Description

Original source: NOIP 2010 Senior Division Preliminary Round · Problem Completion

Beacon towers are crucial military defense installations, typically built along major transportation routes or strategic locations. In case of military activity, smoke signals are used during the day and fire signals at night to relay information.

Between two cities, there are $n$ beacon towers, each with a certain cost to send a signal. To ensure accurate transmission of intelligence, at least one out of every consecutive $m$ beacon towers must send a signal. Given $n$, $m$, and the cost of each beacon tower, compute the minimum total cost required to accurately transmit information between the two cities.

Input Format

The first line contains $n$ and $m$, representing the number of beacon towers $n$ and the consecutive tower count $m$.

The second line contains $n$ integers, each denoting the cost $a_i$ of the corresponding beacon tower.

Output Format

Output a single integer, the minimum cost.

Sample 1

Send signals from the 2nd and 5th beacon towers.

5 3
1 2 5 6 2

4

Data Range and Hint

For all data, $1\le n,m\le 2\times 10^5$, and $1\le a_i\le 1000$.