Description:
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 < 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.
Input Format:
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 < d_{i+1}$$$).
Output Format:
Print one integer — maximum amount of burles Vasya can earn.
Note:
None