5. Bread and Circuses
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Petya returned from school and realized that he forgot to buy bread. He also understood that he needed to act quickly: in $$$n$$$ minutes, a broadcast of an important match of his favorite football team will begin.

The journey from Petya's home to the bakery takes $$$t$$$ minutes, and it will take him the same amount of time to return. Buying bread will take one minute. It is guaranteed that $$$2 \cdot t + 1 \le n$$$.

Petya was already ready to go for the bread, but it started to drizzle. According to the weather forecast, it will rain for the next $$$n$$$ minutes, and for each $$$j$$$-th minute, the amount of precipitation $$$d_j$$$ that will fall during that minute is known.

Petya wants the total amount of precipitation that will fall while he is outside to be as low as possible.

Petya can delay leaving home, and he can wait a bit in the bakery and not leave immediately after making the purchase. The main thing is that he must return home no later than $$$n$$$ minutes. Your task is to determine the minimum possible total amount of precipitation that will fall while Petya is outside.

Input

The first line contains an integer $$$n$$$ $$$(n \le 3 \cdot 10^5)$$$ — the maximum time by which Petya must be home.

The second line contains an integer $$$t$$$ ($$$t\ge 1$$$, $$$2t+1\le n$$$) — the time it takes Petya to walk from home to the bakery or back.

Each of the following $$$n$$$ lines contains one integer $$$d_j$$$ $$$(1 \le d_j \le 10^3, \, j = 1, 2, \ldots, n)$$$ — the amount of precipitation that will fall in the $$$j$$$-th minute.

Output

Output an integer — the minimum possible total amount of precipitation that will fall while Petya is outside.

Scoring

Solutions that work correctly for $$$n \le 100$$$ will be scored with 40 points.

Example
Input
18
4
5
2
1
4
2
1
11
3
2
1
14
12
3
1
2
1
6
2
Output
15
Note

In the example from the statement, Petya should leave home in the 3rd minute. The amount of precipitation that will fall during his time outside will be $$$1 + 4 + 2 + 1 = 8$$$. He will make the purchase in the 7th minute, after which, starting from minute $$$\#8$$$, he can head back.

The best solution for him would be to wait until the 13th minute: if he leaves the bakery at that moment, the amount of precipitation that will fall during his time outside will be $$$3 + 1 + 2 + 1 = 7$$$.

The total amount of precipitation will be $$$15$$$. It can be verified that in other cases, the amount of precipitation will be greater.