问题描述

"Teishi-zushi"是一家简单的日本料理餐厅，只有一个圆形柜台。柜台的外周长为$C$米。顾客不能进入柜台。

Nakahashi进入了Teishi-zushi，并被引导到柜台。现在，柜台上有$N$块寿司（用于配饭的醋饭和海鲜等）。从Nakahashi站立的地点到第$i$个寿司放置的地点的顺时针距离为$x_i$米。而且，第$i$块寿司的营养价值为$v_i$千卡。

Nakahashi可以自由地绕柜台走。当他到达一个寿司放置的地点时，他可以吃掉那个寿司并摄取其中的营养（寿司自然消失）。然而，在行走过程中，他每走1米，就会消耗1千卡的能量。

每当他满足时，他可以从任意位置离开餐厅（不需要返回初始位置）。总体而言，在离开之前，他最多能摄取多少营养？也就是说，摄取的总营养减去消耗的总能量的最大可能值是多少？假设没有其他顾客，并且不会有新的寿司放置在柜台上。此外，由于Nakahashi的身体中有足够的营养，请假设无论他走多远和消耗多少能量，他都不会因饥饿而死亡。

约束条件

• $1 ≤ N ≤ 10^5$
• $2 ≤ C ≤ 10^{14}$
• $1 ≤ x_1 < x_2 < ... < x_N < C$
• $1 ≤ v_i ≤ 10^9$
• 输入中的所有值都是整数。

分数

• 如果通过满足$N ≤ 100$的测试集，则可获得300分。

---

输入

输入格式如下：

$N\space C$ $x_1\space v_1$ $x_2\space v_2$ $:$ $x_N\space v_N$

输出

如果Nakahashi在离开餐厅之前最多可以摄取$c$千卡的营养，请输出$c$。

---

示例输入1

3 20
2 80
9 120
16 1

示例输出1

191

柜台上有三块寿司，周长为20米。如果他顺时针从初始位置走两米，他可以吃一块80千卡的寿司。再顺时针走七米，他可以吃一块120千卡的寿司。如果他现在离开，总共摄取的营养是200千卡，总消耗的能量是9千卡，因此他在离开之前最多能摄取191千卡的营养，这是最大可能的值。

---

示例输入2

3 20
2 80
9 1
16 120

示例输出2

192

第二和第三个寿司被交换了位置。同样，如果他顺时针从初始位置走两米，他可以吃一块80千卡的寿司。这一次，如果他逆时针再走六米，他可以吃一块120千卡的寿司。如果他现在离开，总共摄取的营养是200千卡，总消耗的能量是8千卡，因此他在离开之前最多能摄取192千卡的营养，这是最大可能的值。

---

示例输入3

1 100000000000000
50000000000000 1

示例输出3

0

即使唯一的寿司离柜台太远而不适合存储在32位整数中，其营养价值很低，因此他应该立即离开而不做任何事情。

---

示例输入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

示例输出4

6500000000

以上所有示例输入都包含在部分得分测试集中。