3565. 忽冷忽热

单点时限: 2.0 sec

内存限制: 512 MB

章鱼哥来到闵行住宿:宿舍楼内置的浴室很完美,只可惜洗澡的水是忽冷忽热的。

为了简化问题,我们假设洗澡的水变化有一定的规律,具体来说,在章鱼哥洗澡的时间 $[0,z]$ 内,假设章鱼哥一开始调整的水温是 $y$,那么会在 $0$ 到 $t_1$ 这段时间内,均匀地变化为 $y + \Delta y_1$,在 $t_1$ 到 $t_2$ 这段时间内,均匀地变化为 $y + \Delta y_2$,如此往复,在 $t_{n-1}$ 到 $t_n$ 这段时间内,均匀地变化为 $y + \Delta y_n$,形成一条折线。

章鱼哥能洗澡当且仅当现在的水温 $t$ 满足 $37 \le t \le 37+h$。他只能在洗澡前调整水温。求他最多能洗多久的澡?

输入格式

第一行两个整数 $n$, $h$ ($1 \le n \le 10^5, 0 \le h \le 2 \cdot 10^5$)。

接下来 $n$ 行,分别表示 $(t_1, \Delta y_1)$, $(t_2, \Delta y_2)$, $\ldots$, $(t_n, \Delta y_n)$ ($1 \le t_1 < t_2 < \cdots < t_n = z \le 10^6$, $-10^5 \le \Delta y_i \le 10^5$, $t_i, \Delta y_i$ 是整数)。

输出格式

输出能获得最大的洗澡时间。相对误差或绝对误差不超过 $10^{-6}$。

样例

Input
3 2
50 5
75 2
100 5
Output
53.3333333333
Input
2 2
500 2
1000 1
Output
1e3
Input
1 1
1 1
Output
1
Input
1 0
1 1
Output
0

提示

水温可以降到任意低。即使这不符合物理定律。

样例 1 解释:

6 人解决,14 人已尝试。

6 份提交通过,共有 91 份提交。

8.1 EMB 奖励。

创建: 2 年,4 月前.

修改: 2 年,4 月前.

最后提交: 2 年,2 月前.

来源: 2018 华东师范大学校赛

题目标签