Problem Description
Peanut is playing a card game today, and in this card game, Bradley deals him a set of N cards in a row and lays them in a row from left to right. Each of this card contains an integer, which can be positive or negative. Bradley then asks Peanut to select up to K non-overlapping ranges of length up to L. He then has to pick up those cards and sum them. Help Peanut find the maximum sum.
Input
The first line of input contains three integers, N, K and L.
The second line of input contains N integers, which represent the cards given to Peanut by Bradley.
Output
Your program should output one integer, stating the maximum sum Peanut can obtain.
Limits
1 ≤ N, K, L ≤ 3 000.
Each of the integers on the cards will not have an absolute value of more than 100 000.
Subtask 1 (3%): All integers in the cards will be non-negative. L = N.
Subtask 2 (11%): K = 1, L = N.
Subtask 3 (14%): K = 1.
Subtask 4 (25%): 1 ≤ N, K, L ≤ 200.
Subtask 5 (47%): No other constraints apply.
Subtask 6 (0%): Sample testcases.
Sample Input 1
7 1 7
5 -9 3 -2 5 5 -3
Sample Output 1
11
Explanation for Sample 1
5 -9 (3 -2 5 5) -3
Sample Input 2
10 3 3
1 -2 3 4 8 -6 7 -8 9 -10
Sample Output 2
31
Explanation for Sample 2
1 -2 (3 4 8) -6 (7) -8 (9) -10