問題文
UT 大学有一个叫做帐篷列的社团介绍活动。道路长度为 L ,umg 君沿着这条路单行到位置 0 到位置 L 。umg 君有一个叫作气力的参数,其初始值为 T 假设为如此。这里,T 为整数值。umg 同学每走 1 步,如果气力低于 T ,气力会恢复 1 次。当气力为 T 时,不会恢复。
道路上有 N 个帐篷,i 号帐篷的位置在 X_i 。 umg 先生在到达 i 号帐篷时会遭到社团招募,精力会减少 A_i 。如果此时精力低于 0 ,umg 先生会当场倒下。umg 先生在途中不倒下到达位置
所需的初始精力值为 L 精力初始值 T 的最小值。
制約
- 所有输入均为整数。
- 1 \leq N \leq 2\times 10^5
- N \lt L \leq 10^9
- 0\lt X_1 \lt X_2 \lt \cdots \lt X_N \lt L
- 1 \leq A_i \leq 10^9 \ (1\leq i \leq N)
入力
输入是按以下格式从标准输入给出的。
N L X_1 A_1 X_2 A_2 \vdots X_N A_N
出力
答案 请打印除以 1 行输出。
入力例1
2 7 1 5 4 4
出力例1
6
气力的初始值 T=6 开始,精力将会发生如下变化。到达第
- 1 个帐篷时,精力减少,为 5 ,在到达第 1 。
- 2 个帐篷之前精力恢复,为 3 ,在到达 4 。
- 2 个帐篷时,精力减少,为 4 ,在到达第 0 。
- 位置 7 之前精力恢复,为 3 ,以精力 3 的状态结束帐篷列。
气力的初始值 T=5 开始时,2 号帐篷处的气力会降到 0 以下,因此答案是 6 。 对于
入力例2
8 11 2 6 3 10 4 8 5 7 7 7 8 1 9 9 10 2
出力例2
42