Frog
Time Limit : 3000/1000ms (Java/Other) Memory Limit : 65536/65536K (Java/Other)
Total Submission(s) : 6 Accepted Submission(s) : 2
Problem Description
A little frog named Fog is on his way home. The path's length is N (1 <= N <= 100), and there are many insects along the way. Suppose the <br>original coordinate of Fog is 0. Fog can stay still or jump forward T units, A <= T <= B. Fog will eat up all the insects wherever he stays, but he will <br>get tired after K jumps and can not jump any more. The number of insects (always less than 10000) in each position of the path is given. <br>How many insects can Fog eat at most? <br>Note that Fog can only jump within the range [0, N), and whenever he jumps, his coordinate increases. <br>
Input
The input consists of several test cases. <br>The first line contains an integer T indicating the number of test cases. <br>For each test case: <br>The first line contains four integers N, A, B(1 <= A <= B <= N), K (K >= 1). <br>The next line contains N integers, describing the number of insects in each position of the path.
Output
each test case: <br>Output one line containing an integer - the maximal number of insects that Fog can eat. <br>
Sample Input
1<br>4 1 2 2 <br>1 2 3 4 <br>
Sample Output
8
Source
ECJTU 2008 Summer Contest