Summer Institute @ University of Central Florida: Contest 1, Problem 2

Bernard the bear has finally woken up from hibernation and is very hungry. He walks over to the nearest river and sees all the different kinds of fish swimming in a line, some fish more delicious looking than others. Sneaking up behind one of the fish, Bernard swipes and catches the fish. In the process, he was seen by the nearby fish and they swam away, not looking to become lunch today. Distraught that he can't catch all the fish for his lunch, Bernard now wonders what the most delicious lunch he can have given that some of the nearby fish will swim away after each time he catches one.

Given the deliciousness of fish in their current order in the river and an integer representing the distance of which fish can see, find the max sum of deliciousness that Bernard can have for his lunch. Each fish is located one unit away from another. If the fish can see $k$ units away, and Bernard catches a fish at location $x$, the fish from $[x-k,x-1]$ and $[x+1,x+k]$ will swim away and cannot be caught.

Input Specification

The first line will contain two space separated integers, $n$ $(1\le n\le {10}^5)$ and $k$ $(1\le k\le 10)$, representing the number of fish in the river and the distance away the fish can see Bernard catch another fish. The next line will contain $n$ space separated integers $x_i$ $(1\le x_i\le {10}^9)$, representing the deliciousness of fish $i$.

Output Specification

Output a single integer on a line by itself, representing the maximum sum of deliciousness that Bernard can have for his lunch.

Sample Input 1

10 2
20 4 12 17 19 15 2 5 1 13

Sample Output 1

52

Sample Input 2

10 4
8 28 1 9 28 2 9 1 27 2

Sample Output 2

55