1351 - Group

Time Limit: 1s Memory Limit: 128MB

Submissions: 1066 Solved: 266
Description
There is a sequence of N numbers. Cut them into not more than K groups without changing their order, and each group must consist of at least L numbers. From left to right, the value of the i-th group is the sum of all numbers in the group multiplying i. Give me the minimum sum of all the values.
Input
The first line is a number T indicating the total number of test cases.(T<=20) Then T cases, for each case: First line is three numbers N, K, L which are descripted above.(1<=N<=20000, 1<=L<=200, 1<=K<=100) Then N numbers ranged in [-1000, 1000].
Output
For each case, output the minimum sum in a line.
Sample Input
2
5 3 1
3 -2 -1 -4 5
5 3 2
3 -2 -1 -4 5
Sample Output
-1
1
Hint
To get the best answer you can try: Case 1: (3)(-2 -1 -4 5) or (3)(-2)(-1 -4 5) Case 2: (3 -2)(-1 -4 5)
Source
Hust Monthly 10.04.05/Zehua HONG