Problem Background

Little K is daydreaming again. He finds himself in his fantasy, having conquered a vast empire.

Problem Description

Little K's empire consists of \( n \) cities. There is a bidirectional highway connecting city \( i \) and city \( i+1 \), and traveling on this highway takes \( a_i \) units of time.

To care for the well-being of his people, Little K decides to make regular visits. Each time, he will travel from city 1 to city \( n \) and visit the cities along the way, with the destination being city \( n \).

Moreover, he has a teleportation device with a radius of \( k \), meaning he can teleport to city \( i-k \) or city \( i+k \). If the target city number is less than 1, it defaults to 1, and if it is greater than \( n \), it defaults to \( n \).

However, his teleportation device is low on power and can only be used once. Due to certain reasons, he wants to complete his visits as quickly as possible. Therefore, he asks the Minister of Transportation what the fastest time is.

Note: He does not have to visit all cities, and using the teleportation device does not consume time.

Input Format

Two lines. The first line contains \( n \) and \( k \).

The second line contains \( n-1 \) integers, where the \( i \)-th integer represents \( a_i \).

Output Format

A single integer representing the answer.

Sample Input and Output

Sample Input #1

4 0
1 2 3

Sample Output #1

6

Sample Input #2

4 1
1 2 3

Sample Output #2

3

Notes

Sample Explanation 1:

For both sample 1 and 2, the diagram is as follows:

Without using the teleportation device, the answer is 6, which can be proven to be the minimum.

Sample Explanation 2:

Teleport from city 3 to city 4, the answer is 3, which can be proven to be the minimum.

Data Range:

For all data, \( a_i > 0 \)

见题面 Input 部分

见题面 Output 部分