AIOC Banner

Problem: Time Warp

Want to try solving this problem? You can submit your code online if you log in or register.


Time Warp

Input File: standard input
Output File: standard output
Time Limit: 1 second
Memory Limit: 32 MB

You are a time traveller. You love concerts. Obviously, you combine these two hobbies.

Your time machine is powered by units called turbo warpers. When you use a y-year turbo warper, it propels you exactly y years into the past.

\includegraphics[width=12cm]{samplewarp}

The above diagram shows the effect of using a two-year turbo warper at the end of year 3. It's just a jump to the left. You then continue stepping to the right like normal. You can't use the warper again (but if you have another two-year turbo warper on hand, you can still use that one).

Further rules on time travel:

Some years were amazing years for concert goers: who can forget the first time Huey Lewis sang "The Power of Love"? Others were pretty terrible, like the time The Who were gatecrashed by an overdressed fellow wearing a celery stick. You've gone through every year in music history, and assigned it an integer audio score - the higher the score, the better the year was.

You wish to plot a path through time, whch must start at the beginning of year 1 and finish at the end of year X, maximising the total audio score of years you experience. Note that for each year you live through, its audio score is added to your total regardless of how many times you have experienced that year before.

Input

Output

Output should consist of a single integer: the maximum possible total audio score you can achieve under the conditions described above.

Sample Input 1

6 3
6
9
0
8
7
-3
2
3
2

Sample Output 1

74

Sample Input 2

3 6
-5
2
-5
1
1
2
2
3
3

Sample Output 2

-4

Explanation

\includegraphics[width=9cm]{warppath1}

In the first sample case, you use all your available turbo warpers for a total audio score of:

6+9+6+9+0+8+7+8+9+0+8+7+-3 = 74

\includegraphics[width=4.5cm]{warppath2}

In the second sample case, you use only your 1-year turbo warpers for a total score of:

-5 + 2 + 2 + 2 + -5 = -4

Constraints & Subtasks

The following constraints apply to all subtasks:

For each subtask, the following special constraints also apply:

 


Privacy statement
© Australian Mathematics Trust 2001-2021

Contact: training@orac.amt.edu.au
Page generated: 22 September 2021, 11:35am AEST