Description

The land that Little K has conquered contains a total of $n$ cities. City $i$ and city $i+1$ are connected by a two-way highway, and traveling along this road takes time $a_i$.

In order to care about the people’s lives, Little K decides to make regular visits. Each time, he will travel from city $1$ to city $n$ and visit the cities he passes through. The destination must be city $n$.

Moreover, he has a teleporter with teleport radius $k$, meaning he can teleport to $i-k$ and $i+k$. If the target city index is less than $1$, it becomes $1$; if it is greater than $n$, it becomes $n$.

However, his teleporter does not have enough power and can only be used once. Also, for some reason, he wants to finish the visits as quickly as possible, so he asks you, the Minister of Transportation, what the minimum time is.

Note: He does not need to visit all cities, and using the teleporter costs no time.

Input Format

Two lines. The first line contains two positive integers $n, k$.

The second line contains $n-1$ integers, where the $i$-th one denotes $a_i$.

Output Format

One integer, indicating the answer.

4 0
1 2 3

6

4 1
1 2 3

3

Hint

Sample Explanation 1:

The illustrations for samples 1 and 2 are both the following image:

If the teleporter is not used and you just walk directly, the answer is $6$. It can be proven that this is the minimum.

Sample Explanation 2:

Use it at $3$ and teleport to $4$. The answer is $3$. It can be proven that this is the minimum.

Constraints:

For all testdata, $n \ge 2$, $k \ge 1$, $a_i > 0$.

Translated by ChatGPT 5