human
Solve in Python:
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 $\lfloor \frac{k}{c} \rfloor$ 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^9) — 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.
assistant
#Here is the Python program you requested.

from functools import *
from time import time
from heapq import *

# 
# def measure_time(fun):
#     def wrapper(*args, **kwargs):
#         begin = time()
#         rv = fun(*args, **kwargs)
#         end = time()
#         print(end - begin)
#         return rv
#     return wrapper
#
#
# def our_cache(func):
#     memo = [-1]*(max+1)
#
#     @wraps(func)
#     def wrapper(arg):
#         if memo[arg] == -1:
#             memo[arg] = func(arg)
#         return memo[arg]
#     return wrapper

def main():
    n, c = [int(x) for x in input().split()]
    a = [int(x) for x in input().split()]

    if c > n:
        print(sum(a))
        return

    b = n * [0]
    s = 0
    h = []
    for i in range(n):
        s = s + a[i] if i <= c-1 else s + a[i] - a[i-c]
        heappush(h, (a[i], i))
        if i <= c-2:
            b[i] = s
        else:
            while i-h[0][1] >= c:
                heappop(h)
            v1 = b[i-c] + s - h[0][0]
            v2 = a[i] + b[i-1]
            b[i] = min(v1, v2)

    print(b[-1])

def __starting_point():
    main()
__starting_point()