Nguồn: Free Contest

KC97 Studio vừa cho ra mắt trò chơi điện tử "Bắn bong bóng" trên hệ điều hành FC. Trò chơi diễn ra như sau:

Có ~N~ quả bong bóng xuất hiện trên màn hình từ trái qua phải, được đánh số từ ~1~ đến ~N~. Quả bong bóng thứ ~i~ được ghi số ~A_i~. Người chơi sẽ có ~K~ lượt ném phi tiêu, mỗi lượt sẽ ném vào một quả bong bóng. Gọi ~p_i~ là quả bong bóng được chọn ở lượt ~i~. Điểm số người chơi nhận được ở lượt thứ ~i~ là ~i \times A_{p_i}~.

Ngoài ra, việc chọn bong bóng phải thỏa mãn điều kiện sau:

• Với mọi ~i~ ~(1 < i \le N)~ thì ~1 \le p_i - p_{i-1} \le M~.

Hãy tính tổng điểm số cao nhất mà người chơi có thể đạt được.

Input

• Dòng đầu tiên ghi ba số nguyên dương ~N~, ~M~, ~K~ ~(M \le N \le 2.10^5,~ ~K \le min(n, 200))~ - số quả bong bóng, hằng số ~M~ và số lượt ném.
• Dòng tiếp theo gồm ~N~ số nguyên dương ~A_1, A_2, ..., A_N~ ~(1 \le A_i \le 10^9)~ - các con số được ghi trên các quả bong bóng.

Output

• In ra một số nguyên duy nhất là tổng số điểm cao nhất có thể đạt được.

Samples

Sample Input 1

7 1 3
1 9 2 4 5 3 7

Sample Output 1

32

Sample Input 2

7 2 3
1 9 2 4 5 3 7

Sample Output 2

35

Sample Input 3

7 6 3
1 9 2 4 5 3 7

Sample Output 3

40

Clarification

• Ở ví dụ thứ nhất, ta chọn các quả bong bóng ở vị trí ~5~, ~6~ và ~7~. Tổng số điểm sẽ là ~1 \times 5 + 2 \times 3 + 3 \times 7 = 32~.
• Ở ví dụ thứ hai, ta chọn các quả bong bóng ở vị trí ~4~, ~5~ và ~7~. Tổng số điểm sẽ là ~1 \times 4 + 2 \times 5 + 3 \times 7 = 35~.
• Ở ví dụ thứ ba, ta chọn các quả bong bóng ở vị trí ~2~, ~5~ và ~7~. Tổng số điểm sẽ là ~1 \times 9 + 2 \times 5 + 3 \times 7 = 40~.

Scoring

• Subtask ~1~ (~20\%~ số điểm): ~N \le 20~
• Subtask ~2~ (~20\%~ số điểm): ~N \le 2000,~ ~K \le 20~
• Subtask ~3~ (~30\%~ số điểm): ~K \le 20~
• Subtask ~4~ (~30\%~ số điểm): Không có ràng buộc gì thêm