← 返回题目列表

Codeforces · 1107/G

G. Vasya 和最大利润

中文机器翻译题面 查看原题

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