Minimum Travel Time with Teleporter

There are \(n\) cities numbered from 1 to \(n\). For each \(i\) from 1 to \(n-1\), there is a bidirectional highway between city \(i\) and city \(i+1\) that takes \(a_i\) time to travel. Little K visits by traveling from city 1 to city \(n\) (the destination must be city \(n\)).

Additionally, Little K has a teleporter with a radius \(k\). From any city \(i\), he can teleport to city \(i-k\) or \(i+k\). Note that if \(i-kn\), he teleports to city \(n\). The teleporter can be used at most once and does not consume any time.

Little K does not need to visit all cities along the way. He wants to know the minimum total travel time required to reach city \(n\) from city 1 using highways and at most one teleport.

Input/Output Format: See the sections below.

inputFormat

The first line contains two integers (n) and (k) ((n \ge 1), (k \ge 1)), representing the number of cities and the teleporter's radius. The second line contains (n-1) integers (a_1, a_2, \ldots, a_{n-1}), where (a_i) is the travel time between city (i) and city (i+1).

outputFormat

Output a single integer: the minimum travel time required to go from city (1) to city (n).

sample

5 2
1 100 1 1

2