Consider a board with fields numbered from 0 to n. On each field i ∈ {1, ..., n} there is an integer (possibly negative) number a_i ∈ Z. 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 a_i 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.

Input

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 a_i. There are no values given for fields 0 and n, because these positions will be always clear at the end of the game.

Output

A single integer giving the required answer on a separate line for each test case.

Example

Input:
5
5
15
5
8
15

Output:
43

Input:
5
2
15
5
8
15

Output:
30