Material Farming

View as PDF

Submit solution

Points: 7 (partial)
Time limit: 1.0s
Memory limit: 128M

Author:
Problem type

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 N days. Every day the amount of silver awarded for completion changes and is denoted by a_i. Additionally, after completing the final map, it requires K days to replenish its resources before it can be completed again. This means that if the map is completed on day i and K=0, skyflare can complete another run on day i+1. Impatient to wait the full K 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 N days?

Input Specification

The first line contains two space-separated integers N, K (0 \le K < N \le 2 \cdot 10^5)

The second line contains N integers, the silver awarded for completion of the final map on a given day, a_1, a_2, ... , a_N (1 \le a_i \le 10^4)

Output Specification

Output a single integer, the maximum amount of silver that skyflare can farm.

Subtasks

Subtask 1 (20%)

N \le 1000

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

There are no comments at the moment.