Đ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 xi và có ci 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.
Input: Có cấu trúc như sau:
- Dòng đầu ghi hai số nguyên N và k (k ≤ 2.000.000);
- N dòng tiếp theo, dòng thứ i ghi hai số nguyên ci và xi (ci ≤ 1.000.000);
- Các số trong tệp cách nhau ít nhất một dấu cách.
Output: Số nấm nhiều nhất Bờm thu hoạch được.
Ví dụ:
|
THUHOACH.INP |
THUHOACH.OUT |
Giải thích |
|
4 3 4 7 10 15 2 2 5 1 |
11 |
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. |
Ràng buộc:
- Có 30 % test N ≤ 1.000 và xi ≤ 1.000.000 tương ứng 30 % số điểm;
- Có 30% test N ≤ 50.000 và xi ≤ 1.000.000 tương ứng 30 % số điểm;
- Có 40 % test N ≤ 100.000 và xi ≤ 1.000.000.000 tương ứng 40 % số điểm.
