Cashback

2000ms

262144K

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 $\text{[math]}$ 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 a_i (1 ≤ a_i ≤ 10⁹) — elements of a.

Output:

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

Sample Input:

3 5
1 2 3

Sample Output:

Sample Input:

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

Sample Output:

Sample Input:

7 2
2 3 6 4 5 7 1

Sample Output:

Sample Input:

8 4
1 3 4 5 5 3 4 1

Sample Output:

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.

Informação

Provedor Codeforces

Código CF940E