Vui Hội Trăng Rằm
Đêm Trung Thu, đám trẻ trong xóm A rủ nhau lập một đoàn múa lân. Xóm có N ngôi nhà xếp thành một hàng, đánh số từ 1 đến $N$. Nếu đoàn múa trước cửa nhà thứ \(i\), gia chủ sẽ lì xì \(a_i\) đồng.
Để kiếm được nhiều tiền nhất, đám trẻ được tự chọn một đoạn nhà liên tiếp từ nhà \(L\) đến nhà \(R\) \((1 \le L \le R \le N)\): xuất phát ở nhà \(L\), đi lần lượt qua từng nhà và dừng lại ở nhà \(R\). Các nhà nằm ngoài đoạn này không được tính.
Trên đường đi, ở mỗi nhà đoàn sẽ múa hoặc nghỉ (chỉ đi ngang qua, không nhận lì xì). Vì múa lân rất mệt, đoàn phải tuân theo hai quy tắc:
- Không múa quá \(K\) nhà liên tiếp.
- Mỗi đợt nghỉ là một dãy các nhà liên tiếp mà đoàn không múa. Càng về sau đoàn càng mệt, nên kể từ lúc xuất phát, đợt nghỉ thứ \(i\) phải kéo dài qua ít nhất \(i\) nhà.
Hãy tính số tiền lì xì lớn nhất mà đoàn có thể nhận được.
Dữ liệu
- Dòng đầu tiên chứa hai số nguyên \(N, K \ (1\le N, K \le 10^5)\);
- Dòng tiếp theo chứa \(N\) số nguyên \(a_i \ (0\le a_i \le 10^9)\).
Kết quả
- Kết quả bài toán.
Chấm điểm
- Subtask 1 (30%): \(N \le 20\).
- Subtask 2 (20%): \(N \le 1000\).
- Subtask 3 (50%): Không có giới hạn gì thêm.
Ví dụ
Ví dụ 1
input
5 3
1 2 3 2 1
output
7
Ví dụ 2
input
10 2
1 4 3 2 5 4 3 2 1 2
output
19
Comments