CF1107G Vasya and Maximum Profit

题目描述

有 $n$ 道题目，而我们可亲可敬的 $\tt Coin\; Collection\; Function$（下文简称 $\tt FCC$）正以极高的热情筹备着比赛！

如果 $\tt FCC$ 将第 $i$ 道题作为比赛题，$\tt FCC$ 需要支付 $c_i$ 元给工作人员。但是 $\tt FCC$ 每增加一道题，就可以获得 $a$ 元的“自愿捐助”款。

现在 $\tt FCC$ 想选择一个连续区间 $[l,r]$ 作为比赛题。

题目的难度需要相差不大，否则容易引起选手憎恨。每个题目有一个难度 $d_i$ ，$\tt FCC$ 会额外支付 $\max_{i=l}^{r-1}(d_{i+1}-d_{i})^2$ 元来堵住媒体的嘴。特别的，若 $l=r$ 则无这一笔额外款项。

$\tt FCC$ 精打细算，想要获得最多的钱。请你告诉 $\tt FCC$ ，最多能赚多少钱吧！

输入格式

第一行是 $n,a$ ，含义如题。

接下来 $n$ 行，第 $i+1$ 行是两个数 $d_i,c_i$ ，描述一道题。变量含义如题。

输出格式

仅一行一个整数。需要输出的值见题面。

数据范围与提示

$1\le n\le 3\times 10^5$ 且 $1\le a\le 10^9$ 且 $1\le d_i<d_{i+1}\le 10^9$ 且 $1\le c_i\le 10^9$ 。

输入输出样例 #1

输入 #1

5 10
1 15
5 3
6 11
7 2
11 22

输出 #1

13

输入输出样例 #2

输入 #2

3 5
1 8
2 19
3 11

输出 #2

0