1867: Group

There is a sequences of N numbers, cut them into no more than K groups without change their order, and each group at least L numbers. Calculate the sum of all the groups‘ value. From left to right, the value of the i-th group is the the sum of all numbers in the group multiply i. Give me the minimum sum.

The first line is a number T indicate the number of test cases.(T < 20) Then T cases, for each case: First line is three numbers N, K, L as description.(1<=L<=N<=20000, 1<=K<=100) Then N numbers ranged in [-1000, 1000].

For each case, output the minimum sum in a line.

2
5 3 1
3 -2 -1 -4 5
5 3 2
3 -2 -1 -4 5

-1
1

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)