Minimum Travel Time

Problem Description

There are $n$ cities, numbered $1, 2, \dots, n$. Between city $i$ and city $i+1$ there is a bidirectional road, and traversing it takes time $a_i$.

You start from city $1$ and want to reach city $n$. Apart from the roads, you also have a teleporter with a range of $k$: once used, it takes you directly from city $i$ to city $i-k$ or city $i+k$; if the target index is less than $1$ it is treated as $1$, and if greater than $n$ it is treated as $n$. The teleporter can be used at most once, and using it consumes no time.

You do not need to visit every city. Find the minimum time needed to travel from city $1$ to city $n$.

Input Format

Two lines. The first line contains two positive integers $n, k$ ($1 \le n \le 10^6$, $0 \le k < n$).

The second line contains $n-1$ integers; the $i$-th number is $a_i$ ($a_i \le 10^8$).

Output Format

Output a single integer: the minimum travel time.

Sample Input 1

4 0
1 2 3

Sample Output 1

6

Sample Input 2

4 1
1 2 3

Sample Output 2

3