The minimum spanning tree of a graph is defined as a tree which contains all the vertices, and does so using the smallest accumulative weight of edges.

You are given a graph in the shape of a line: it has ~N~ vertices and ~N-1~ edges, where the ~i~-th edge connects vertices ~i~ and ~i+1~, using weight ~w_i~. You are also given an integer ~K~: there exists an arbitrary number of "network trampolines," indicating that a weightless edge connects the ~i~-th vertex to the ~i+K~-th vertex, given that both exist, for all values of ~i~. You are also allowed to use the other existing edges as necessary.

All edges are undirected.

Find the minimum spanning tree of the graph by outputting the sum of the weights of all encompassed edges.

Input Specification

On the first line, there will be the integer ~N~, followed by a space, followed by the integer ~K~.

On the next line, there will be ~N-1~ space-separated integers, the ~i~-th being ~w_i~, the weight of the edge connecting the ~i~-th vertex with the ~i+1~-th vertex. (It should be assumed that the vertices are numbered from ~1~ to ~N~.)

Constraints

For all subtasks:

~1 \le K \le 100\,000~

For all ~i~ from ~1~ to ~N-1~, ~0 \le w_i \le 1\,000~.

Subtask 1 [35%]

~2 \le N \le 12~

Subtask 2 [20%]

~2 \le N \le 1\,001~

Subtask 3 [45%]

~2 \le N \le 100\,000~

Output Specification

Print a single integer, the combined weight of the graph's minimum spanning tree.

Sample Input 1

3 2
3 5

Sample Output 1

3

Explanation for Sample 1

There are three vertices in this graph. 1 and 2 are connected by an edge of weight 3, 2 and 3 by one of weight 5, and it can be deduced that, since ~K=2~ and ~3-1=2~, 1 and 3 are connected by an edge of weight 0. The minimum spanning tree consists of the 0-weight edge and the 3-weight edge, which spans all the vertices.

Sample Input 2

5 2
5 6 7 8

Sample Output 2

5

Explanation for Sample 2

There are five edges: edges of weight 0 exist from 1 to 3, 3 to 5, and 2 to 4. Take all of these edges, along with the edge connecting 1 and 2, and the minimum spanning tree is complete.

Sample Input 3

5 3
5 6 7 8

Sample Output 3

11