Alice and Bob have become the winners of the TV quiz, and now they have to choose their prizes. There are n prizes to choose from, numbered from 1 to n.
The distribution of prizes is as follows. The organizers of the TV quiz give the winners a positive integer k (1 ≤ k ≤ n / 3). First, Alice chooses for herself any k successive numbers of prizes. Then Bob chooses k successive prize numbers for himself, while he cannot choose numbers that Alice has already chosen. After that, the winners collect their chosen prizes.
Alice knows Bob well, and for each prize she has figured out its value to Bob, which is a positive integer. Alice is offended by Bob and wants to choose her prizes so that the total value of the prizes that Bob gets is as small as possible. At the same time, Alice does not care what prizes she gets.
It is required to write a program that, given the information about the value of the prizes and the value of k, will determine for what minimum value of x Alice can ensure that Bob cannot choose prizes with a total value greater than x.
Input file format
The first line of the input file contains two integers: n — the total number of prizes and k — the number of consecutive prize numbers that each of the winners must choose (3 ≤ n ≤ 100,000, 1 ≤ k ≤ n / 3). The second line contains n positive integers: a1, a2, …, an. Each prize has its value to Bob (1 ≤ ai ≤ 109 ).
Output file format
The output file must contain a single number — the minimum value of x for which Alice can ensure that Bob cannot choose prizes with a total value greater than x.
Example
Input:
10 2
1 2 4 5 2 4 2 2 1 6
Output:
7
Explanation of the example
In the example above, Alice can, for example, choose the 4th and 5th prizes. After that, it is optimal for Bob to choose the 9th and 10th prizes with a total value of 7.