F.A.Q
Hand In Hand
Online Acmers
Problem Archive
Realtime Judge Status
Authors Ranklist
 
     C/C++/Java Exams     
ACM Steps
Go to Job
Contest LiveCast
ICPC@China
Best Coder beta
VIP | STD Contests
    DIY | Web-DIY beta
Author ID 
Password 
 Register new ID

Horse

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 262144/262144 K (Java/Others)
Total Submission(s): 246    Accepted Submission(s): 129


Problem Description
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.
 

Input
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.
 

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

Sample Input
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
 

Sample Output
-1 17 25
 

Hint

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.
 

Source
 

Statistic | Submit | Discuss | Note
Hangzhou Dianzi University Online Judge 3.0
Copyright © 2005-2024 HDU ACM Team. All Rights Reserved.
Designer & Developer : Wang Rongtao LinLe GaoJie GanLu
Total 0.000000(s) query 1, Server time : 2024-10-12 16:48:24, Gzip enabled