Board
Consider a board with fields numbered from 0 to n. On each field i ∈ {1, ..., n} there is an integer (possibly negative) number ai ∈ ℤ. A player is given a pawn on field number 0. Player can move the pawn back and front on distance not exceeding k. A pawn can visit all the fields many 0 and n many times, but it can stop moving definitively only at position n (player decides on when to stop). Whenever a pawn visits field i, the field is cleared and the number ai is removed (if the field wasn’t clear before the move). A player wants to maximize the sum of numbers on non-cleared fields.
Write a program that reads on the standard input the description of a game, and writes on standard output the value of an optimal strategy. On the first line of input you are given the number n (1 ≤ n ≤ 1000). On the second line of input you are given the parameter k (1 ≤ k ≤ n). In the next n − 1 lines of the input you are given single integer numbers, where on line i + 2 you are given the number ai. There are no values given for fields 0 and n, because these positions will be always clear at the end of the game.
Example
For the input:
5
5
15
5
8
15
the answer is:
43
And for the input
5
2
15
5
8
15
the answer is:
30