Candy Crush

View as PDF

Submit solution

Points: 7
Time limit: 1.0s
Memory limit: 64M

Problem type

Leyang loves to play Candy Crush in his spare time. In level 4761 of the game, he is given a row of N candies, each with a tastiness a_i. His goal is to consume as much tastiness as possible. In a single move, he chooses a candy at position i to eat, consuming a_i tastiness. This will cause all candies within a distance R to be crushed. Formally, his total tastiness increases by a_i, and all candies a_{i-R} \ldots a_{i+R} are deleted and left as empty space. He may not choose a candy whose explosion reaches into empty space or over the left and right edges. If he continues to make moves until he is unable to, how tasty can Leyang become what is the maximum total tastiness Leyang can consume?


1 \le N, R \le 2 \times 10^5

1 \le a_i \le 10^9

Input Specification

The first line contains two numbers: N, the number of candies, and R, the explosion radius.

The second line contains N space separated integers, each corresponding to a_i for 1\le i\le N.

Output Specification

Output one integer: the maximum total tastiness Leyang can consume.

Sample Input

8 1
2 7 30 35 36 32 1 1

Sample Output


Explanation for Sample Output

Leyang eats the candy with tastiness 30, leaving 2 X X X 36 32 1 1 (X indicating empty space).

He then eats the candy with tastiness 32, leaving 2 X X X X X X 1. He cannot make any more moves so his total consumed tastiness is 30 + 32 = 62.


There are no comments at the moment.