Problem E
Roller Coaster Fun
Jimmy and his friends like to visit large theme parks. In the current theme park there are many roller coasters which then are categorized by Jimmy. He assigns a fun value to each coaster; however, the fun decreases with each run.
More formally: for a specific roller coaster
Jimmy tries to maximize the total fun until he leaves the park. Can you tell Jimmy how much fun he can gain for a given time?
Input
The input consists of a single test case.
The first line contains the integer
The following
The next line contains a positive integer
Output
For each of the
Sample Input 1 | Sample Output 1 |
---|---|
2 5 0 5 7 0 7 4 88 5 6 7 |
88 5 5 7 |
Sample Input 2 | Sample Output 2 |
---|---|
1 100 3 2 5 2 3 4 5 100 |
100 100 197 197 435 |