Horse

There is a horse which can jump over trees and he has to jump N trees sequentially.
Initially, the horse has zero energy.
Jumping trees, he loses energy (one unit of energy per unit of height) and he gets points as the amount of left energy (Left energy can be less than 0).
And his final score is the sum of all points that the horse gets after each jump.
The horse can do two types of tricks.
*Just before every jump, he can eat a tree. Of course, he jumps over the eaten tree which has no height.
*Just after every jump, he can have a break. After each break, he restores energy. It means that his energy becomes the total sum of heights of all eaten trees.
But he has limits, he can have at most K breaks and eat at most M trees.
You have to find the maximum score that the horse can gets.

The first line contains an integer T (1 <= T <= 10) denoting the number of test cases.
The first line of each test case contains three integers N (1 <= N <= 10000), K (0 <= K <= min (50, N - 1)) and M (0 <= M <= min (50, N)).
The second line of each test case contains N integers h1, h2 … hn (1 <= hi <= 10000), where hi denote the height of ith tree.

For each test case, print the maximum score that the horse can gets.

3
4 1 1
4 2 3 1
4 2 4
4 2 3 1
10 2 3
2 3 4 5 6 2 7 4 3 1

-1
17
25

For the first test case, the answer is that the horse eats the first tree and has a break after the second jump.
For the second test case, the horse has breaks after the first and third jump and eats all trees.

2019 Multi-University Training Contest 4