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 翻译