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

---

hide comments

	hodobox: 2016-07-04 16:31:54 very concisely: Given fields 0,1,2...N, choose a subset of fields so that from any field the nearest chosen field to the right is at most K units away, such that the sum of all not chosen fields is maximum possible.
	Vamsi Krishna Avula: 2014-12-29 11:58:03 I think the problem statement is not explicit, so here goes my version: you are given a board of fields numbered from 0 to "n" and you can move to any field from the present field provided it is "k" units away. If you place the pawn on a field, you clear it there by making its value 0. now you have to choose some fields such that you are able to cover all the fields. You can choose such fields in many ways (you can simply choose all the n + 1 fields), but you have to choose them in such a way that sum of uncleared fields is maximum. And finally 0 and "n" numbered fields are always cleared. Hope it helps. :)
	Samuel Nacache: 2014-03-15 19:48:45 Can someone explain second case? If he can't move exceeding 2, can't he move one by one?
	Rishabh Sharma: 2013-12-29 13:16:25 Someone please explain the question. The language is very confusing. What does "A pawn can visit all the fields many 0 and n many times" mean? Also, what does the statement " Player can move the pawn back and front on distance not exceeding k" mean? Last edit: 2013-12-29 15:01:57
	Goldie: 2013-12-11 16:47:14 Be careful with negative numbers. Last edit: 2013-12-29 19:42:12