题目描述

日本料理店「停止寿司」是一家只有一个圆形吧台的简约餐厅。吧台的外周长度为 $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

输入

3 20
2 80
9 120
16 1

输出

191

样例 2

输入

3 20
2 80
9 1
16 120

输出

192

样例 3

输入

1 100000000000000
50000000000000 1

输出

0

样例 4

输入

15 10000000000
400000000 1000000000
800000000 1000000000
1900000000 1000000000
2400000000 1000000000
2900000000 1000000000
3300000000 1000000000
3700000000 1000000000
3800000000 1000000000
4000000000 1000000000
4100000000 1000000000
5200000000 1000000000
6600000000 1000000000
8000000000 1000000000
9300000000 1000000000
9700000000 1000000000

输出

6500000000

说明/提示

限制条件

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