AT_utpc2020_a.Row of Tents

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$。

输入通过标准输入给出，格式如下：

$N$ $L$ $X_1$ $A_1$ $X_2$ $A_2$ $\cdots$ $X_N$ $A_N$

请输出一个整数，表示所需的最小初始气力 $T$。

限制条件

• 所有输入均为整数。
• $1 \leq N \leq 2 \times 10^5$
• $N < L \leq 10^9$
• $0 < X_1 < X_2 < \cdots < X_N < L$
• $1 \leq A_i \leq 10^9\ (1 \leq i \leq N)$

样例解释 1

当初始气力 $T=6$ 时，气力的变化如下：

• 到达第 $1$ 个帐篷时，气力减少 $5$，剩余 $1$。
• 到达第 $2$ 个帐篷前，气力恢复 $3$，变为 $4$。
• 到达第 $2$ 个帐篷时，气力减少 $4$，变为 $0$。
• 走到位置 $7$ 前，气力恢复 $3$，以气力 $3$ 结束活动。

如果初始气力 $T=5$，则在第 $2$ 个帐篷处气力会降到 $0$ 以下，因此答案为 $6$。

由 ChatGPT 4.1 翻译