Bạn đã trở thành một cao thủ cờ vua và giành chiến thắng trong giải đấu cờ vua trẻ mở rộng, nhận được các phần thưởng từ nhà tài trợ. Các gói quà được sắp xếp thành một hàng, đánh số từ 1 đến \(n\), và gói quà thứ \(i\) có giá trị \(a_{i}\).

Ban tổ chức đã đưa ra một quy định rằng mỗi phần thưởng sẽ là một nhóm các gói quà liên tiếp, trong đó chênh lệch giữa hai gói quà bất kỳ không vượt quá \(k\). Vì bạn là nhà vô địch, bạn được ưu ái chọn hai phần thưởng mà không có gói quà chung. Hãy tìm tổng giá trị quà lớn nhất mà bạn có thể nhận được.

Yêu cầu: Tìm tổng giá trị quà lớn nhất có thể chọn được.

Dữ liệu vào:

+ Dòng thứ nhất chứa hai số nguyên dương \(n,\ k\ (n \leq {3.10}^{5},\ k \leq 10^{9})\) là số gói quà nhà tài trợ chuẩn bị và độ chênh lệch lớn nhất giữa hai gói quà theo quy định.

+ Dòng thứ hai gồm \(n\) số nguyên \(a_{i}\ (a_{i} \leq 10^{9})\) lần lượt là giá trị của từng món quà.

Kết quả:

+ Gồm một dòng duy nhất là giá trị lớn nhất nhận được.

Ví dụ:

Ràng buộc:

+ Subtask 1: 25% số test đầu tiên có \(n \leq 30;\)

+ Subtask 2: 25% số test tiếp theo có \(n \leq 10^{3};\)

+ Subtask 3: 25% số test tiếp theo có \(n \leq 10^{5}\) và \(a_{i}\) tăng dần;

+ Subtask 4: 25% số test còn lại không có ràng buộc gì.