Cashback
Description
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 
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.
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 a single integer — the smallest possible sum of values of these subarrays of some partition of a.
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.
Samples
3 5
1 2 3
6
12 10
1 1 10 10 10 10 10 10 9 10 10 10
92
7 2
2 3 6 4 5 7 1
17
8 4
1 3 4 5 5 3 4 1
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.