← 返回题目列表

Codeforces · 1041/D

D. 滑翔机

中文机器翻译题面 查看原题

一架飞机在距地面 $$$h$$$ 米的恒定高度飞行。我们假设它从 $$$(-10^9, h)$$$ 点飞向与 $$$Ox$$$ 轴平行的点 $$$(10^9, h)$$$。

滑翔机在飞机内,随时准备开始飞行(为了简单起见,我们考虑只有当飞机的坐标为整数时他才可以开始)。从飞机上跳下来后,他会沿着与飞机相同的方向飞行,平行于$$$Ox$$$轴,每秒飞过一个单位距离。自然,他也会降临;因此他的第二个坐标每秒会减少一个单位。

某些段上有上升气流,每个段都由两个数字 $$$x_1$$$ 和 $$$x_2$$$ ($$$x_1 < x_2$$$) 表示其端点。没有两个段有任何共同点。当滑翔机位于其中一个分段内时,他不会下降,因此他的第二个坐标每秒保持不变。滑翔机仍然沿着 $$$Ox$$$ 轴飞行,每秒移动一个单位的距离。

如果滑翔机在 $$$1$$$ 处跳出,他将在 $$$10$$$ 处停止。否则,如果他在$$$2$$$处跳出,他将在$$$12$$$处停止。

如果滑翔机可以选择任意整数坐标从飞机上跳下并开始飞行,则确定从滑翔机飞行开始点到飞行结束点沿 $$$Ox$$$ 轴的最大距离。接触地面后,滑翔机完全停止,因此如果他的第二个坐标是 $$$0$$$,他就无法滑翔通过上升气流段。

输入

第一行包含两个整数 $$$n$$$ 和 $$$h$$$ $$$(1 \le n \le 2\cdot10^{5}, 1 \le h \le 10^{9})$$$ ——分别是上升气流段的数量和飞机飞行的高度。

接下来的 $$$n$$$ 行包含两个整数 $$$x_{i1}$$$ 和 $$$x_{i2}$$$ $$$(1 \le x_{i1} < x_{i2} \le 10^{9})$$$ - 第 $$$i$$$ 上升气流段的端点。没有两个线段相交,并且它们按升序给出。

输出

打印一个整数——如果滑翔机可以在任意整数坐标处开始飞行,则滑翔机从跳下飞机的点到着陆点可以沿 $$$Ox$$$ 轴飞行的最大距离。

示例

输入 #1

3 4
2 5
7 9
10 11

输出 #1

10

输入 #2

5 10
5 7
11 12
16 20
25 26
30 33

输出 #2

18

输入 #3

1 1000000000
1 1000000000

输出 #3

1999999999

注意

在第一个例子中,如果滑翔机可以在$$$(2, 4)$$$处跳出,那么着陆点是$$$(12, 0)$$$,所以距离是$$$12-2 = 10$$$。

在第二个示例中,滑翔机可以从 $$$(16,10)$$$ 飞到 $$$(34,0)$$$,距离为 $$$34-16=18$$$。

在第三个示例中,滑翔机可以从 $$$(-100,1000000000)$$$ 飞到 $$$(1999999899,0)$$$,因此距离为 $$$1999999899-(-100)=1999999999$$$。