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