Chọn K đoạn con

Cho dãy $n$ số nguyên $p_1,p_2,\dots ,p_n$.

Bạn cần chọn ra $k$ đoạn con:

$$[l_1,r_1],[l_2,r_2],\dots ,[l_k,r_k]$$

thoả mãn đồng thời hai điều kiện:

• Các đoạn rời nhau và xếp theo thứ tự tăng dần: $1\le l_1\le r_1<l_2\le r_2<\dots <l_k\le r_k\le n$.
• Mỗi đoạn có độ dài đúng bằng $m$: $r_i-l_i+1=m$ với mọi $i$.

Hãy chọn sao cho tổng các phần tử nằm trong $k$ đoạn đó là lớn nhất, tức là cực đại hoá

$$\sum _{i=1}^k\sum _{j=l_i}^{r_i}{p}_j.$$

Lưu ý rằng bắt buộc phải chọn đủ $k$ đoạn, kể cả khi một số phần tử trong đoạn mang giá trị nhỏ. Ràng buộc $m\times k\le n$ bảo đảm luôn tồn tại ít nhất một cách chọn hợp lệ.

Dữ liệu vào

• Dòng đầu chứa ba số nguyên $n$, $m$, $k$.
• Dòng thứ hai chứa $n$ số nguyên $p_1,p_2,\dots ,p_n$.

Dữ liệu ra

In ra một số nguyên duy nhất là tổng lớn nhất có thể.

Ràng buộc

• $1\le m\times k\le n\le 5000$
• $0\le p_i\le {10}^9$

Ví dụ