## Candy Crush

View as PDF

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

Author:
Problem type

Leyang loves to play Candy Crush in his spare time. In level 4761 of the game, he is given a row of candies, each with a tastiness . His goal is to consume as much tastiness as possible. In a single move, he chooses a candy at position to eat, consuming tastiness. This will cause all candies within a distance to be crushed. Formally, his total tastiness increases by , and all candies 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?

#### Input Specification

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

The second line contains space separated integers, each corresponding to for .

#### 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

62

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