Trong một ngày hội Công nghệ tại thành phố Tương Lai, các robot đều có khả năng trình diễn các tiết mục võ thuật. Có ~n~ robot đứng thành một hàng theo thứ tự từ ~1~ đến ~n~. Robot thứ ~i~ có chỉ số năng lượng trình diễn là ~a_i~.

Mỗi tiết mục biểu diễn gồm một nhóm robot liên tiếp nhau trong hàng. Một tiết mục được gọi là ổn định nếu độ chênh lệch năng lượng trình diễn giữa robot mạnh nhất và yếu nhất trong tiết mục đó không vượt quá ~k~. Biết rằng, hai tiết mục được chọn phải không giao nhau, có nghĩa là không có robot nào tham gia cả hai tiết mục.

Tổng năng lượng của một tiết mục được tính là tổng năng lượng của tất cả các robot trong tiết mục đó. Ban tổ chức muốn chọn ra ~2~ tiết mục biểu diễn xuất sắc nhất, là hai tiết mục ổn định, không giao nhau.

Hãy tìm tổng năng lượng lớn nhất của ~2~ tiết mục được chọn.

Input

• Dòng thứ nhất chứa hai số nguyên dương ~n~, ~k~ ~(2 \le n \le 3 \cdot 10^5, k \le 10^9)~ là số lượng robot và độ chênh lệch lớn nhất giữa hai robot theo quy định.

• Dòng thứ hai gồm ~n~ số nguyên ~a_i~ ~(0 < a_i \le 10^9)~ lần lượt là chỉ số năng lượng trình diễn của từng robot.

Output

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

Scoring

Sample Input 1

5 2
1 2 3 4 5

Sample Output 1

15