AT_arc096_b.[ABC095D] Static Sushi

日本料理店「停止寿司」是一家只有一个圆形吧台的简约餐厅。吧台的外周长度为 $C$ 米，顾客不能进入吧台内部。

中桥君进入餐厅，被带到吧台旁边。现在，吧台上放有 $N$ 贯寿司。其中第 $i$ 贯寿司位于从中桥君所在位置顺时针方向前进 $x_i$ 米处，具有 $v_i$ 千卡的营养价值。

中桥君可以自由地沿着吧台的外周行走。当他到达有寿司的位置时，可以吃掉该寿司并获得其营养价值（寿司会消失）。不过，行走时每走 $1$ 米会消耗 $1$ 千卡的能量。

当他觉得满意时，可以从任意位置离开餐厅（不必回到起始位置）。请问，在离开餐厅前，他最多可以净获得多少千卡的能量？也就是说，离开前所获得的总营养价值减去消耗的能量的最大值是多少？另外，餐厅内没有其他顾客，也不会有新的寿司被添加。中桥君体力充沛，无论消耗多少能量都不会饿死。

输入以如下格式从标准输入读入。

$N$ $C$
$x_1$ $v_1$
$x_2$ $v_2$
$\vdots$
$x_N$ $v_N$

输出在离开餐厅前净获得的最大千卡能量 $c$。

限制条件

• $1 \leq N \leq 10^5$
• $2 \leq C \leq 10^{14}$
• $1 \leq x_1 < x_2 < \cdots < x_N < C$
• $1 \leq v_i \leq 10^9$
• 输入中的所有值均为整数。

部分分

• 对于 $N \leq 100$ 的测试点，满分为 $300$ 分。

样例解释 1

吧台外周为 $20$ 米，有 $3$ 贯寿司。中桥君从起点顺时针走 $2$ 米，可以吃到 $80$ 千卡的寿司。再顺时针走 $7$ 米，可以吃到 $120$ 千卡的寿司。此时离开餐厅，获得的总营养为 $200$ 千卡，消耗能量为 $9$ 千卡，净获得 $191$ 千卡，这是最大值。

样例解释 2

第 $2$ 贯和第 $3$ 贯寿司的位置互换。中桥君从起点顺时针走 $2$ 米，吃到 $80$ 千卡的寿司。此时改变方向，逆时针走 $6$ 米，吃到 $120$ 千卡的寿司。此时离开餐厅，获得的总营养为 $200$ 千卡，消耗能量为 $8$ 千卡，净获得 $192$ 千卡，这是最大值。

样例解释 3

唯一的寿司距离太远且营养价值低，因此应什么都不做直接离开。

样例解释 4

以上所有输入样例均包含在部分分的测试点中。

由 ChatGPT 4.1 翻译