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: HARD
Tags: Dynamic programming

Data structures

Mathematics

Greedy algorithms
Skill types: Dynamic programming

Data structures

Greedy algorithms

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


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


class SegTree:

	def __init__(self, init_val, ide_ele, segfunc):
		self.n = len(init_val)
		self.num = 2 ** (self.n - 1).bit_length()
		self.ide_ele = ide_ele
		self.segfunc = segfunc
		self.seg = [ide_ele] * 2 * self.num
		for i in range(self.n):
			self.seg[i + self.num] = init_val[i]
		for i in range(self.num - 1, 0, -1):
			self.seg[i] = self.segfunc(self.seg[2 * i], self.seg[2 * i + 1])

	def add(self, k, x):
		k += self.num
		self.seg[k] += x
		while k:
			k = k >> 1
			self.seg[k] = self.segfunc(self.seg[2 * k], self.seg[2 * k + 1])

	def query(self, l, r):
		if r <= l:
			return self.ide_ele
		l += self.num
		r += self.num
		lres = self.ide_ele
		rres = self.ide_ele
		while l < r:
			if r & 1:
				r -= 1
				rres = self.segfunc(self.seg[r], rres)
			if l & 1:
				lres = self.segfunc(lres, self.seg[l])
				l += 1
			l = l >> 1
			r = r >> 1
		res = self.segfunc(lres, rres)
		return res

	def __str__(self):
		arr = [self.query(i, i + 1) for i in range(self.n)]
		return str(arr)
INF = 10 ** 18

def main():
	(n, k) = map(int, input().split())
	A = list(map(int, input().split()))
	if k > n:
		print(sum(A))
		exit()
	if k == n:
		print(sum(A) - min(A))
		exit()
	res = []
	from collections import deque
	d = deque([])
	for i in range(n):
		while d:
			if d[0] <= i - k:
				d.popleft()
			else:
				break
		while d:
			if A[d[-1]] > A[i]:
				d.pop()
			else:
				break
		d.append(i)
		if i - k + 1 >= 0:
			res.append(A[d[0]])
	seg = SegTree(res, -INF, max)
	for i in range(len(res)):
		t = max(0, seg.query(0, i - k + 1))
		seg.add(i, t)
	print(sum(A) - seg.query(0, seg.n))
main()


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 main():
	(n, c) = [int(x) for x in input().split()]
	a = [int(x) for x in input().split()]
	if c > n:
		print(sum(a))
		exit(0)
	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])
main()


def queries(l, r):
	mini = float('inf')
	while l <= r:
		if l % 2 == 1:
			mini = min(mini, sgn_tree[l])
			l += 1
		if r % 2 == 0:
			mini = min(mini, sgn_tree[r])
			r -= 1
		l = l >> 1
		r = r >> 1
	return mini
(n, c) = map(int, input().split())
arr = list(map(int, input().split()))
sgn_tree = [0 for i in range(2 * n)]
sgn_tree[n:] = arr
for i in range(n - 1, 0, -1):
	sgn_tree[i] = min(sgn_tree[2 * i], sgn_tree[2 * i + 1])
dp = [0 for i in range(n)]
for i in range(n):
	if i - c >= -1:
		dp[i] = max(dp[i - c] + queries(n + i - c + 1, n + i), dp[i - 1])
s = sum(arr)
print(s - dp[n - 1])