Vasya 真的厌倦了这些积分(来自问题 F),现在想自己赚钱!他决定举办一场比赛来获取利润。
Vasya 有 $$$n$$$ 问题可供选择。它们的编号从 $$$1$$$ 到 $$$n$$$。第 $$$i$$$ 问题的难度为 $$$d_i$$$。此外,问题按照其难度递增的顺序给出。所有任务的难度都是成对不同的。为了将第 $$$i$$$ 问题添加到竞赛中,您需要向其作者支付 $$$c_i$$$ burles。对于比赛中的每个问题,Vasya 都会获得 $$$a$$$ burles。
为了创建竞赛,他需要选择连续的任务子部分。
因此比赛的总收入计算如下:
- 如果 Vasya 将问题 $$$i$$$ 参加比赛,他需要向其作者支付 $$$c_i$$$ ;
- 对于比赛中的每个问题 Vasya 都会获得 $$$a$$$ burles;
- 让 $$$gap(l, r) = \max\limits_{l \le i < r} (d_{i + 1} - d_i)^2$$$。如果 Vasya 将索引从 $$$l$$$ 到 $$$r$$$ 的所有任务都参加比赛,他还需要支付 $$$gap(l, r)$$$。如果 $$$l = r$$$ 则 $$$gap(l, r) = 0$$$。
计算 Vasya 通过连续完成一段任务可以获得的最大利润。
输入
第一行包含两个整数 $$$n$$$ 和 $$$a$$$ ($$$1 \le n \le 3 \cdot 10^5$$$, $$$1 \le a \le 10^9$$$) — 分别是建议任务的数量和单个问题的利润。
接下来的 $$$n$$$ 行包含两个整数 $$$d_i$$$ 和 $$$c_i$$$ ($$$1 \le d_i, c_i \le 10^9, d_i < d_{i+1}$$$)。
输出
打印一个整数 — Vasya 可以获得的最大 burles 数量。
示例
输入 #1
5 10 1 15 5 3 6 11 7 2 11 22
输出 #1
13
输入 #2
3 5 1 8 2 19 3 11
输出 #2
0