Thu hoạch

Nhà của An có $N$ thửa ruộng liên tiếp. Thửa ruộng thứ $i$ có giá trị $w_i$, là số tiền dự kiến thu được sau khi bán sản phẩm và trả chi phí gặt. Giá trị của thửa ruộng có thể là số âm do số tiền bán sản phẩm ít hơn chi phí gặt.

An có $K$ máy gặt và đang tìm các vị trí đặt chúng để hoạt động cùng lúc (cả $K$ máy đều phải hoạt động). Mỗi máy gặt khi hoạt động phải gặt trên một đoạn gồm đúng $L$ thửa ruộng liên tiếp. Mỗi thửa ruộng chỉ được gặt một lần.

Yêu cầu: Hãy chọn vị trí đặt các máy gặt sao cho tổng số tiền dự kiến thu được là lớn nhất.

Dữ liệu vào

• Dòng đầu tiên gồm ba số nguyên dương $N$, $K$, $L$ ($1\le N\le 5000$, $1\le K\times L\le N$).
• Dòng thứ hai gồm $N$ số nguyên $w_1,w_2,\dots ,w_N$ ($|w_i|\le {10}^9$).

Dữ liệu ra

In ra một số nguyên duy nhất là tổng số tiền dự kiến thu được.

Ràng buộc

• $1\le N\le 5000$, $1\le K\times L\le N$.
• $|w_i|\le {10}^9$.

Subtasks

• Subtask 1 ($30\%$ số điểm): $N\le 20$.
• Subtask 2 ($30\%$ số điểm): $K=1$.
• Subtask 3 ($40\%$ số điểm): $N\le 5000$.

Ví dụ