← 返回题目列表

AtCoder · utpc2020_a

A. 一排帐篷

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

問題文

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