Nhân dịp nghỉ lễ, An được bố mẹ đưa lên nhà chị họ ở thành phố chơi, Bình chị họ của An rất vui mừng khi gặp cô em họ đã lâu không gặp. Hai chị em chơi đùa rất vui và không muốn chia tay nên Bình muốn tặng An một số món quà làm kỉ niệm. Bình có \(n\) món đồ chơi, và đặt chúng từ 1 đến \(n\), đồ chơi thứ \(i\) có giá trị là \(a_i\). Trong lúc chọn quà, Bình yêu cầu An không được chọn \(k\) món đồ chơi liên tiếp.

Yêu cầu: Hãy giúp An chọn các đồ chơi với tổng giá trị lớn nhất.

Input

• Dòng 1 : gồm 2 số \(n\) và \(k\) cách nhau bởi khoảng trắng.
• Dòng 2 : chứa n số nguyên \(a_1, a_2, \ldots, a_n\) \((0 \leq a_i \leq 10^6)\).

Output

• Ghi một số nguyên duy nhất là tổng giá trị các món đồ chơi lớn nhất mà An có thể chọn được.

Scoring

• Subtask \(1\) (\(50\%\) số điểm): \(n \leq 10^3\).
• Subtask \(2\) (\(50\%\) số điểm): \(n \leq 10^6\).

Example

5 3
6 19 8 7 13 

45