skyflare is playing the new hit game, Gremlin Impact.
In Gremlin Impact, the rarest drop in the game, silver, is obtained by completing the final map. skyflare is trying to farm as much silver as he can over the next days. Every day the amount of silver awarded for completion changes and is denoted by . Additionally, after completing the final map, it requires days to replenish its resources before it can be completed again. This means that if the map is completed on day and , skyflare can complete another run on day . Impatient to wait the full days, he purchased a booster that allows him to bypass the previous rule one time. Boosters are expensive so skyflare wants to make the most of it.
Can you help him farm the most silver in days?
Input Specification
The first line contains two space-separated integers
The second line contains integers, the silver awarded for completion of the final map on a given day,
Output Specification
Output a single integer, the maximum amount of silver that skyflare can farm.
Subtasks
Subtask 1 (20%)
Subtask 2 (80%)
No further constraints.
Sample Input 1
6 3
5 5 5 5 5 5
Sample Output 1
15
Sample Input 2
11 2
1 5 2 1 4 6 7 3 2 1 2
Sample Output 2
20
Comments