Muốn chọn một số vị trí trên tuyến đường để đặt trạm sạc xe điện, công ty XNOVA tiến hành chia tuyến đường thành \(n\) vị trí liên tiếp, đánh số từ \(1\) đến \(n\). Kết quả khảo sát cho thấy, lượng xe có nhu cầu sạc mỗi ngày ở vị trí thứ \(i\) (\(1 \le i \le n\)) là \(a_i\).

Để tránh quá tải hệ thống điện, công ty sẽ không đặt trạm sạc ở tất cả \(n\) vị trí khảo sát. Phương án đặt trạm sẽ theo nguyên tắc: trạm sạc đặt tại vị trí khảo sát thứ \(i\) sẽ phục vụ tối đa \(a_i\) lượt xe mỗi ngày và không đặt trạm tiếp theo trong phạm vi \(L\) vị trí liền sau nó. Cụ thể, nếu hai trạm đặt tại các vị trí khảo sát \(i\) và \(j\) (với \(i < j\)) thì phải thỏa mãn \(j - i > L\).

Với phạm vi \(L\) cho trước, công ty muốn tìm phương án đặt trạm sạc tối ưu để tổng số lượt xe tối đa có thể phục vụ mỗi ngày là lớn nhất.

Input

• Dòng đầu tiên ghi hai số nguyên \(n\) và \(L\) cách nhau một dấu cách (\(1 \le n \le 10^6, 0 \le L < n\)).
• Dòng thứ hai ghi \(n\) số nguyên \(a_1, a_2, \dots, a_n\) cách nhau một dấu cách (\(0 \le a_i \le 10^9\)).

Output

• Ghi ra một số nguyên duy nhất là tổng số lượt xe lớn nhất có thể phục vụ mỗi ngày.

Example

7 1
6 10 3 8 5 9 4

27

Scoring

• Subtask \(1\) (\(50\%\) số điểm): \(1 \le n \le 25, 0 \le L < n\).
• Subtask \(2\) (\(30\%\) số điểm): \(1 \le n \le 10^5, L = 1\).
• Subtask \(3\) (\(20\%\) số điểm): \(1 \le n \le 10^6, 0 \le L < n\).