Món quà

Sắp tới trung thu, quầy bán bánh trung thu Kinh Đô (đang bán ở nhà hát thành phố Đông Hà) dự định bán \(1\) tỷ hộp bánh. Tuy nhiên trong quá trình di chuyển, một số hộp bánh đã bị thủng nên bánh đã rơi giữa đường, nhưng hộp thì vẫn còn nên quầy bán vẫn xếp \(1\) tỷ hộp này thành một hàng, sau đó bán. Các hộp bánh chưa bị thủng được được đánh số từ \(1\) tới \(n\) theo thứ tự từ trái sang phải, và mỗi hộp bánh trung thu này đều có giá trị vui vẻ là \(k\). Hộp bánh thứ \(i\) nằm ở vị trí \(x_{i}\) trong \(1\) tỷ hộp bánh và Quân phải trả cho người bán quà \(c_{i}\) đồng để mua.

Quân dự định sẽ mua một đoạn con liên tiếp các hộp bánh chưa thủng, sau đó tặng cho bạn gái của Quân. Gọi vẻ đẹp của dãy hộp là tổng giá trị vui vẻ, trừ đi chi phí, sau đó lại trừ đi bình phương của chêch lệch lớn nhất giữa vị trí của hai món quà liên tiếp trong dãy được chọn (nếu chỉ chọn \(1\) món thì là \(0\)). Quân nhờ các bạn tính vẻ đẹp lớn nhất Quân có thể đạt được nhé !

Input

Dòng đầu tiên chứa hai số nguyên dương \(n\) và \(k\). \((1 \leq n \leq 3 \times 10^5, 1 \leq k \leq 10^9)\).

\(n\) dòng tiếp theo, dòng thứ \(i\) chứa hai số nguyên dương \(x_{i}\) và \(c_{i}\) (dữ liệu đảm bảo dãy \(x\) là một dãy sắp xếp không giảm, và \(1 \leq x_{i}, c_{i} \leq 10^9\))

Output

Dòng duy nhất là vẻ đẹp lớn nhất có thể.

Example

4 10
2 1
3 2
6 3
8 3

22

6 4
4 4
7 6
9 5
10 3
11 3
12 4

1

7 6
5 3
7 6
8 4
9 6
10 1
13 1
14 6

6

Scoring

\(30\%\) số test tương ứng với \(25\%\) số điểm có \(n \leq 500\).

\(30\%\) số test tương ứng với \(25\%\) số điểm có \(n \leq 3000\).

\(40\%\) số test còn lại không có ràng buộc gì thêm.