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.

Difficulty: interview

Starter code:

Solutions:
str=input().split()
n=int(str[0])
len=int(str[1])
a=[]
Q=[]
F=[]
for i in range(0,n+1):
	a.append(0)
	Q.append(0)
	F.append(0)
sum=0
h=1
t=0
str=input().split()
for i in range(1,n+1):
	a[i]=int(str[i-1])
	sum+=a[i]
	#print (sum)
	while h<=t and Q[h]<=i-len:
		h=h+1
	while h<=t and a[i]<=a[Q[t]]:
		t=t-1
	t=t+1;Q[t]=i;
	if (i<len) :
		F[i]=0
	else :
		F[i]=F[i-len]+a[Q[h]]
	F[i]=max(F[i],F[i-1])
		
print(sum-F[n])


from heapq import *

n, c = map(int, input().split())
a = list(map(int, input().split()))

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

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

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()

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()

from heapq import *

n, c = list(map(int, input().split()))
a = list(map(int, input().split()))

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

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

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])