A12274 | 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 < 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.

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}$ ).

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