Sóc

Sóc là một loài động vật rất nhanh nhẹn, thông minh. Mỗi khi di chuyển chú thường nhảy lên, xuống một cách nhanh chóng. Hôm nay Sóc định dạo chơi trên một dãy đồi núi nhấp nhô, đoạn lên cao, đoạn xuống thấp. Địa hình đồi núi được xác định là một dãy các bậc từ trái sang phải với độ cao khác nhau. Giữa các dãy độ cao này có một mốc qui định là điểm cân bằng, nếu độ cao trên điểm cân bằng thì được gọi là độ cao dương, ngược lại dưới điểm cân bằng thì được gọi là độ cao âm.

Dãy đồi núi bao gồm \(N\) bậc, mỗi bậc có một giá trị độ cao có thể âm hoặc dương nằm trong khoảng \([-10^9, 10^9]\). Ban đầu Sóc ở vị trí điểm cân bằng (độ cao \(0\)), mỗi bước nhảy Sóc có thể nhảy sang phải tối thiểu là \(1\) bước và tối đa là \(K\) bước. Khi dừng lại ở một bậc nào thì độ cao của bậc đó được cộng vào tổng độ cao mà Sóc đã nhảy. Bởi vì có ý định dạo chơi trên dãy núi, nên Sóc sẽ dừng lại ở bất cứ bậc nào miễn sao Sóc đạt được tổng độ cao lớn nhất có thể (Sóc nhảy ít nhất một lần, tức là dừng lại ở một bậc nào đó trong dãy).

Yêu cầu: Bạn hãy xác định xem Sóc sẽ đạt được tổng độ cao lớn nhất là bao nhiêu?

Input

Dữ liệu vào có cấu trúc như sau:

• Dòng đầu tiên chứa \(2\) số nguyên dương \(N\) (\(N \le 10^5\)) và \(K\) (\(K \le 100\)), mỗi số cách nhau một dấu cách.

• Dòng thứ hai chứa \(N\) số nguyên \(A_1, A_2, \ldots, A_N\) (\(-10^9 \le A_i \le 10^9\), \(1 \le i \le N\)) là dãy độ cao của các bậc, các số cách nhau một dấu cách.

Ràng buộc:

• Subtask 1: có \(10/28\) số test tương ứng với \(2{,}5\) điểm có \(N \le 10^4\) và \(K \le 100\).

• Subtask 2: có \(12/28\) số test tương ứng với \(3{,}0\) điểm có \(N \le 9 \cdot 10^4\) và \(K \le 100\).

• Subtask 3: có \(6/28\) số test tương ứng với \(1{,}5\) điểm có \(N \le 10^5\) và \(K \le 100\).

Output

In ra một dòng duy nhất chứa một số nguyên là tổng độ cao lớn nhất mà Sóc đạt được.

Example

Input:

5 2
-5 2 -7 -1 5

Output:

6

Note

Với \(5\) bậc, số bước mỗi lần nhảy tối đa là \(2\), Sóc nhảy như sau: \(0 \to 2 \to 4 \to 5\). Các bậc Sóc đặt chân có độ cao lần lượt là \(2\), \(-1\) và \(5\), tổng độ cao đạt được là \(2 + (-1) + 5 = 6\). Không có cách nhảy nào cho tổng lớn hơn \(6\).