statement

​ 小 W 是个懒惰的 OIer，他正在打游戏。游戏有 $n$ 个关卡，由于这是开放世界，他可以以任意顺序通关这个游戏。

​ 每个关卡有一个轻松值和一个无聊值，越在后面打某个管卡，其轻松值就会越大。第 $i$ 个关卡的初始轻松值是 $a_i$，初始无聊值是 $b_i$。这款游戏设计非常精妙，如果小 W 第 $i$ 个通关的是 $p_i$ 个关卡，那么他得到的轻松值是 $a_{p_i} + i*k$，无聊值是 $b_{p_i} + i*k$。而在整个游戏过程中，小 W 获得的轻松值是每个关卡轻松值的最小值，无聊值是每个关卡无聊值的最大值。

​ 现在小 W 想要知道如何让自己获得的轻松值减去自己获得的无聊值最大。也即，找到一个排列 $p$，使得 $\min_i(a_{p_i}+i*k)-\max_i(b_{p_i}+i*k)$ 最大。

input

​ 第一行一个正整数 $n$ 表示游戏的关卡数，以及一个正整数 $k$ ，意义如题面。

​ 之后 $n$ 行，每行两个正整数，分别表示 $b_i, a_i$（请注意这里的顺序）

output

​ 一行一个整数表示游戏过程中 轻松值减去无聊值 的最大值。

sample I

input

2 10
0 15
5 20

output

10

sample II

input

2 10
15 1
20 0

output

-25

sample III

input

11 6
0 74
2 60
4 34
10 36
21 46
26 40
28 38
30 48
50 68
52 68
54 62

output

5

constraints

对于所有数据，满足：$1\le a_i,b_i\le 10^9,k*n\le 10^9,1\le n\le 10^5$

$\textbf{subtask 1 (5 pts)}$：$n\le 20$

$\textbf{subtask 2 (5 pts)}$：$n\le 100$

$\textbf{subtask 3 (10 pts)}$：$n\le 1000$

$\textbf{subtask 4 (10 pts)}$：$n\le 10000$

$\textbf{subtask 5 (20 pts)}$：$k\le 100$

$\textbf{subtask 6 (10 pts)}$：$n\le 50000$

$\textbf{subtask 7 (40 pts)}$：$n\le 100000$