CF1107G.Vasya and Maximum Profit

Vasya got really tired of these credits (from problem F) and now wants to earn the money himself! He decided to make a contest to gain a profit.

Vasya has $n$ problems to choose from. They are numbered from $1$ to $n$. The difficulty of the $i$-th problem is $d_i$. Moreover, the problems are given in the increasing order by their difficulties. The difficulties of all tasks are pairwise distinct. In order to add the $i$-th problem to the contest you need to pay $c_i$ burles to its author. For each problem in the contest Vasya gets $a$ burles.

In order to create a contest he needs to choose a consecutive subsegment of tasks.

So the total earnings for the contest are calculated as follows:

• if Vasya takes problem $i$ to the contest, he needs to pay $c_i$ to its author;
• for each problem in the contest Vasya gets $a$ burles;
• let $gap(l, r) = \max\limits_{l \le i \lt r} (d_{i + 1} - d_i)^2$. If Vasya takes all the tasks with indices from $l$ to $r$ to the contest, he also needs to pay $gap(l, r)$. If $l = r$ then $gap(l, r) = 0$.

Calculate the maximum profit that Vasya can earn by taking a consecutive segment of tasks.

瓦西娅对这些信贷（来自问题 F）感到非常厌倦，现在他想自己赚钱！他决定举办一场竞赛来获利。

瓦西娅有 $n$ 道题目可供选择，编号从 $1$ 到 $n$。第 $i$ 道题的难度为 $d_i$。此外，这些题目按难度严格递增顺序给出，即所有题目的难度两两不同。将第 $i$ 道题加入竞赛需向其作者支付 $c_i$ 卢布。对于竞赛中的每道题，瓦西娅可获得 $a$ 卢布。

为了组织一场竞赛，他必须选择一个连续的子段（即下标连续的一段题目）。

因此，竞赛的总收益按如下方式计算：

• 若瓦西娅将第 $i$ 道题加入竞赛，则需向其作者支付 $c_i$；
• 对于竞赛中的每道题，瓦西娅获得 $a$ 卢布；
• 定义 $gap(l, r) = \max\limits_{l \le i \lt r} (d_{i + 1} - d_i)^2$。若瓦西娅将下标从 $l$ 到 $r$ 的所有题目全部加入竞赛，则他还需额外支付 $gap(l, r)$。若 $l = r$（即仅一道题），则 $gap(l, r) = 0$。

请计算瓦西娅通过选取一个连续的题目子段所能获得的最大利润。

The first line contains two integers $n$ and $a$ ($1 \le n \le 3 \cdot 10^5$, $1 \le a \le 10^9$) — the number of proposed tasks and the profit for a single problem, respectively.

Each of the next $n$ lines contains two integers $d_i$ and $c_i$ ($1 \le d_i, c_i \le 10^9, d_i \lt d_{i+1}$).

第一行包含两个整数 $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 \lt d_{i+1}$）。

Print one integer — maximum amount of burles Vasya can earn.

输出一个整数——Vasya 能赚取的最大卢布金额。