Đang là giữa mùa đông và việc đi ra khỏi nhà là việc vô cùng khó khăn với Bờm. Ngày mai, bạn ấy được phú ông giao việc đi thu hoạch nấm trên khu đất của lão.

Có thể coi khu đất có nấm mà Bờm phải thu hoạch là một đoạn thẳng trên trục số. Có N vị trí có nấm, vị trí thứ i ở điểm $x_i$ và có $c_i$ cây nấm. Vì trời rất lạnh nên Bờm không thể thu hoạch nấm ở những vị trí có khoảng cách vượt quá $k$ so với vị trí đặt sọt đựng nấm. Do vậy Bờm muốn chọn vị trí đặt sọt đựng nấm sao cho tổng số nấm thu hoạch được là nhiều nhất có thể.

Yêu cầu:

• Viết chương trình tính tổng số nấm lớn nhất mà Bờm có thể thu hoạch được khi chọn vị trí đặt sọt tối ưu.

Ràng buộc:

• Có $30$ tes $N\le 1.000$ và $x_i\le 1.000.000$ tương ứng $30$ số diểm;

• Có $30$ test $N\le 50.000$ và $x_i\le 1.000.000$ tương ứng $30$ số điểm;

• Có $40$ test $N\le 100.000$ và $x_i\le 1.000.000.000$ tương ứng $40$ số điểm;

Đầu vào:

Có cấu trúc như sau:

• Dòng đầu ghi hai số nguyên $N$ và $k$ ($k\le 2.000.000$)
• $N$ dòng tiếp theo, dòng thứ $i$ ghi hai số nguyên $c_i$ và $x_i$ ($c_i\le 1.000.000$)

Đầu ra:

Số nấm nhiều nhất Bờm thu hoạch được.

Ví dụ:

Input

4 3
4 7
10 15
2 2
5 1

Output

11

Giải thích:

• Bờm chọn vị trí xuất phát là 4, do đó có thể thu hoạch nấm ở các vị trí 1, 2 và 7 với tổng số nấm là 5 + 2 + 4 = 11.