Câu 4: Cắt hoa (5.0 điểm)

Vườn hoa của nhà Minh nở rộ \(N\) khóm hoa đẹp, khóm hoa thứ \(i\) có \(A_i\) bông hoa. Do nhu cầu của dịp lễ 8/3 lớn nên người lái buôn muốn mua càng nhiều hoa của vườn càng tốt. Tuy nhiên địa hình vườn nhà Minh không thể cắt hoa của \(K\) khóm hoa liên tiếp, vì vậy Minh cần tìm cách cắt hoa sao cho cắt được tổng số bông hoa là nhiều nhất có thể.

Yêu cầu: Hãy xác định số lượng bông hoa nhiều nhất có thể cắt được.

Input

Đọc từ file FCUT.INP gồm:

• Dòng đầu tiên chứa hai số nguyên dương \(N\) và \(K\) \((2 \le K \le N \le 10^5)\);
• Dòng thứ hai chứa \(N\) số nguyên dương \(A_1, A_2, A_3, \dots, A_N\) \((1 \le A_i \le 10^9)\) lần lượt là số bông hoa của mỗi khóm hoa.

Output

Ghi ra file FCUT.OUT một số nguyên là tổng số bông hoa nhiều nhất có thể cắt được.

Example

7 3
2 4 1 5 3 1 6

20

5 2
10 4 7 3 4

21

Scoring

• 40% số test: \(K = 3\)
• 40% số test: \(N \le 10^3, K \le 10^3\)
• 20% số test: \(N \le 10^5, K \le 10^5\)