940_E. Cashback
Since you are the best Wraith King, Nizhniy Magazin «Mir» at the centre of Vinnytsia is offering you a discount.

You are given an array a of length n and an integer c. 

The value of some array b of length k is the sum of its elements except for the <image> smallest. For example, the value of the array [3, 1, 6, 5, 2] with c = 2 is 3 + 6 + 5 = 14.

Among all possible partitions of a into contiguous subarrays output the smallest possible sum of the values of these subarrays.

Input

The first line contains integers n and c (1 ≤ n, c ≤ 100 000).

The second line contains n integers ai (1 ≤ ai ≤ 109) — elements of a.

Output

Output a single integer — the smallest possible sum of values of these subarrays of some partition of a.

Examples

Input

3 5
1 2 3


Output

6


Input

12 10
1 1 10 10 10 10 10 10 9 10 10 10


Output

92


Input

7 2
2 3 6 4 5 7 1


Output

17


Input

8 4
1 3 4 5 5 3 4 1


Output

23

Note

In the first example any partition yields 6 as the sum.

In the second example one of the optimal partitions is [1, 1], [10, 10, 10, 10, 10, 10, 9, 10, 10, 10] with the values 2 and 90 respectively.

In the third example one of the optimal partitions is [2, 3], [6, 4, 5, 7], [1] with the values 3, 13 and 1 respectively.

In the fourth example one of the optimal partitions is [1], [3, 4, 5, 5, 3, 4], [1] with the values 1, 21 and 1 respectively.
```python
from heapq import *
f = lambda: map(int, input().split())
n, c = f()
a = list(f()) + [0] * c
b = [0] * (n + c)
s = 0
h = [(0, -1)]
for i in range(n):
    s += a[i] - a[i - c]
    heappush(h, (a[i], i))
    while h[0][1] <= i - c: heappop(h)
    b[i] = min(b[i - 1] + a[i], b[i - c] + s - h[0][0])
print(b[n - 1])
```