Read problem statements in [Russian], [Mandarin Chinese], [Bengali], and [Vietnamese] as well.

Chef's school semester lasts for n days. Chef's teacher gives the students some homework every day and it is compulsory to turn in the homework by the very next day. Chef knows that the number of minutes needed to complete the homework on the i-th day is H_{i}.

Chef hates homework and wants to spend the minimum amount of time possible in doing homework. Luckily, he has a few tricks up his sleeve. Chef can hack the school records on any given day to make it show that the assigned homework is complete. However to avoid suspicion, Chef will not hack the records strictly more than k days consecutively.

Can you help Chef find the minimum possible total number of minutes that Chef needs to spend on homework?

Note: 
There are multiple test cases in a single file, refer to Input section for more details.
Since the input is large, it is recommended to use fast input/output methods.

------ Input Format ------ 

- The first line contains a single integer T, the number of test cases. The description of the T test cases follow.
- The first line of each test case contains two integers n and k - the number of days in Chef's semester and the maximum number of consecutive days Chef can hack the school's record system.
- The second line of each test case contains n integers, H_{1}, H_{2}, \dots H_{n}, where H_{i} is the number of minutes Chef needs to complete the homework given on the i-th day.

------ Output Format ------ 

- For each test case, print a single line containing an integer, the minimum number of minutes Chef needs to spend on homework.

------ Constraints ------ 

$1 ≤ T ≤ 10^{6}$
$1 ≤ n ≤ 10^{6}$
$1 ≤ k ≤ n$
$0 ≤ H_{i} ≤ 10^{3}$ for all $1 ≤ i ≤ n$
- The sum of $n$ over all test cases is at most $10^{6}$

----- Sample Input 1 ------ 
3
7 3
213 124 156 263 149 6 62
7 1
476 457 232 130 849 95 749
7 2
601 35 45 304 449 452 190
----- Sample Output 1 ------ 
130
682
484
----- explanation 1 ------ 

- In the first test case, Chef does his homework on days $2$ and $6$, taking a total of $H_{2} + H_{6} = 124 + 6 = 130$ minutes. The maximum number of consecutive days that Chef hacks is $3$ (days $3$, $4$, and $5$), which is not more than $k=3$.

- In the second test case, Chef does his homework on days $2$, $4$, and $6$, taking a total of $H_{2} + H_{4} + H_{6} = 457 + 130 + 95 = 682$ minutes.

- In the third test case, Chef does his homework on days $2$ and $5$, taking a total of $H_{2} + H_{5} = 35 + 449 = 484$ minutes.

You can verify that these are indeed the optimal solutions.

Difficulty: VERY_HARD
Tags: Dynamic programming

Data structures

Range queries

Segment trees revisited
Skill types: Dynamic programming

Data structures

Range queries

Starter code:

Solutions:
from collections import deque
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	q = deque([])
	if n == k:
		print(0)
	else:
		for i in range(k + 1):
			while q and a[i] <= a[q[-1]]:
				q.pop()
			q.append(i)
		for i in range(k + 1, n):
			a[i] += a[q[0]]
			while q and q[0] <= i - (k + 1):
				q.popleft()
			while q and a[i] <= a[q[-1]]:
				q.pop()
			q.append(i)
		print(str(min(a[n - k - 1:n])))


from collections import deque
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	arr = list(map(int, input().split()))
	if k >= n:
		print('0')
		continue
	if k == 0:
		print(sum(arr))
		continue
	dp = []
	deq = deque([])
	for i in range(k + 1):
		dp.append(arr[i])
		while deq and deq[-1][0] > dp[i]:
			deq.pop()
		deq.append([dp[i], i])
	for i in range(k + 1, n):
		if deq and deq[0][1] < i - k - 1:
			deq.popleft()
		if deq:
			dp.append(arr[i] + deq[0][0])
		else:
			dp.append(arr[i])
		while deq and deq[-1][0] > dp[i]:
			deq.pop()
		deq.append([dp[i], i])
	print(min(dp[n - k - 1:]))


def E():
	from bisect import bisect, insort
	from collections import deque
	for _ in range(int(input())):
		(n, k) = [int(x) for x in input().split()]
		H = [int(x) for x in input().split()]
		dq = deque()
		dq.append([0, -1])
		for i in range(n):
			while len(dq) and dq[0][1] < i - k - 1:
				dq.popleft()
			ans = H[i] + dq[0][0] if len(dq) else 0
			while len(dq) and dq[-1][0] >= ans:
				dq.pop()
			dq.append([ans, i])
		while len(dq) and dq[0][1] < n - k - 1:
			dq.popleft()
		print(dq[0][0] if len(dq) else 0)
E()


import heapq
from sys import stdin
input = stdin.readline
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	h = list(map(int, input().split()))
	if k == n:
		print(0)
	else:
		dp = [0] * n
		heap = []
		for i in range(k + 1):
			dp[i] = h[i]
			heapq.heappush(heap, (dp[i], i))
		for i in range(k + 1, n):
			mini = -1
			while True:
				(x, y) = heapq.heappop(heap)
				if y >= i - k - 1:
					mini = x
					if y > i - k - 1:
						heapq.heappush(heap, (x, y))
					break
			dp[i] = h[i] + mini
			heapq.heappush(heap, (dp[i], i))
		print(min(dp[-k - 1:]))


from collections import deque
from sys import stdin
input = stdin.readline
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	h = list(map(int, input().split()))
	if k == n:
		print(0)
	else:
		dp = [0] * n
		dq = deque()
		for i in range(k + 1):
			dp[i] = h[i]
			while dq and dq[-1][0] > dp[i]:
				dq.pop()
			dq.append((dp[i], i))
		for i in range(k + 1, n):
			if dq and dq[0][1] < i - k - 1:
				dq.popleft()
			mini = dq[0][0]
			dp[i] = h[i] + mini
			while dq and dq[-1][0] > dp[i]:
				dq.pop()
			dq.append((dp[i], i))
		print(min(dp[-k - 1:]))


import collections
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	q = collections.deque([(0, -1)])
	for (i, h) in enumerate(map(int, input().split())):
		new = q[0][0] + h
		if q[0][1] == i - (k + 1):
			q.popleft()
		while q and q[-1][0] > new:
			q.pop()
		q.append((new, i))
	print(q[0][0])


import sys
from collections import deque

def read(lst=False):
	line = sys.stdin.readline().rstrip()
	if ' ' in line or lst:
		return map(int, line.split())
	return line

def solver():
	if K >= N:
		return 0
	q = deque([0])
	for i in range(1, N):
		if i > K:
			arr[i] += arr[q[0]]
		if q[0] == i - K - 1:
			q.popleft()
		while q and arr[i] <= arr[q[-1]]:
			q.pop()
		q.append(i)
	return min(arr[N - K - 1], arr[q[0]])
T = int(read())
for t in range(T):
	(N, K) = read()
	arr = list(read(True))
	print(solver())
sys.exit()


from collections import deque
t = int(input())
for _ in range(t):
	(n, k) = [int(x) for x in input().split()]
	effort = [int(x) for x in input().split()]
	if n <= k:
		print(0)
		continue
	minQueue = deque()
	dp = []
	for i in range(k + 1):
		dp.append(effort[i])
		while len(minQueue) > 0 and dp[minQueue[-1]] > dp[i]:
			minQueue.pop()
		minQueue.append(i)
	for i in range(k + 1, n):
		if len(minQueue) > 0 and minQueue[0] < i - (k + 1):
			minQueue.popleft()
		dp.append(dp[minQueue[0]] + effort[i])
		while len(minQueue) > 0 and dp[minQueue[-1]] > dp[i]:
			minQueue.pop()
		minQueue.append(i)
	print(min(dp[n - k - 1:n]))


import heapq

def answer():
	dp = [0] + [a[i] for i in range(n)]
	m = []
	done = [False] * (n + 1)
	j = 0
	for i in range(k + 1):
		heapq.heappush(m, (dp[i], i))
	for i in range(k + 1, n + 1):
		x = heapq.heappop(m)
		while done[x[1]]:
			x = heapq.heappop(m)
		dp[i] += x[0]
		heapq.heappush(m, x)
		heapq.heappush(m, (dp[i], i))
		done[j] = True
		j += 1
	x = heapq.heappop(m)
	while done[x[1]]:
		x = heapq.heappop(m)
	return x[0]
for T in range(int(input())):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	print(answer())


from collections import deque
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	h = list(map(int, input().split()))
	dq = deque()
	dp = [[0, 0] for i in range(n + 2)]
	dq.append([0, -1])
	for i in range(n):
		while len(dq) and dq[0][1] < i - k - 1:
			dq.popleft()
		dp[i][0] = h[i]
		if dq:
			dp[i][0] += dq[0][0]
		dp[i][1] = i
		while len(dq) and dq[-1][0] >= dp[i][0]:
			dq.pop()
		dq.append(dp[i])
	while len(dq) and dq[0][1] < n - k - 1:
		dq.popleft()
	if dq:
		print(dq[0][0])
	else:
		print(0)


from sys import stdin
from collections import deque
input = stdin.readline

def func():
	if n == k:
		print(0)
		return
	dq = deque()
	dp = [0 for x in range(n)]
	for i in range(k + 1):
		dp[i] = h[i]
		while dq and dq[-1][0] > dp[i]:
			dq.pop()
		dq.append((dp[i], i))
	for i in range(k + 1, n):
		if dq and dq[0][1] < i - k - 1:
			dq.popleft()
		pref_min = dq[0][0]
		dp[i] = h[i] + pref_min
		while dq and dq[-1][0] > dp[i]:
			dq.pop()
		dq.append((dp[i], i))
	print(min(dp[-k - 1:]))
for _ in range(int(input())):
	(n, k) = map(int, input().strip().split())
	h = list(map(int, input().split()))
	func()


import heapq
n_testcase = int(input())
for testcase in range(n_testcase):
	(n, k) = (int(x) for x in input().split())
	homeworks = [int(x) for x in input().split()]
	if k == n:
		print(0)
		continue
	min_spent_times = homeworks[:k + 1]
	heap = homeworks[:k + 1]
	heapq.heapify(heap)
	pop_heap = []
	for (i, homework) in enumerate(homeworks[k + 1:], start=k + 1):
		min_spent_time = heap[0] + homework
		min_spent_times.append(min_spent_time)
		heapq.heappush(heap, min_spent_time)
		heapq.heappush(pop_heap, min_spent_times[i - (k + 1)])
		while pop_heap and pop_heap[0] == heap[0]:
			heapq.heappop(pop_heap)
			heapq.heappop(heap)
	print(min(min_spent_times[-k - 1:]))


import heapq

def minSum(arr, n, k):
	dp = [0] * n
	if n < k:
		return 0
	elif n == k:
		return min(arr)
	h = [(arr[i], i) for i in range(k)]
	heapq.heapify(h)
	m = h[0]
	for i in range(k, n):
		uv = arr[i] + m[0]
		heapq.heappush(h, (uv, i))
		if m[1] == i - k:
			heapq.heappop(h)
			while h[0][1] < i - k:
				heapq.heappop(h)
			m = h[0]
	while h[0][1] < n - k:
		heapq.heappop(h)
	return h[0][0]
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	H = list(map(int, input().split()))
	print(minSum(H, n, k + 1))


from collections import deque

def f(nums, k):
	dp = [0] * len(nums)
	dp[0] = nums[0]
	d = deque([(nums[0], 0)])
	for i in range(1, len(nums)):
		dp[i] = nums[i] + d[0][0]
		while d and d[-1][0] < dp[i]:
			d.pop()
		d.append((dp[i], i))
		if i - k == d[0][1]:
			d.popleft()
	return dp[-1]
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	l = list(map(int, input().split()))
	nums = [0] + [-i for i in l] + [0]
	print(-f(nums, k + 1))