ADZEN is a popular advertising firm in your city that owns all $n$ billboard locations on Main street. The city council passed a new zoning ordinance mandating that no more than $\boldsymbol{\mbox{k}}$ consecutive billboards may be up at any given time. For example, if there are $n=3$ billboards on Main street and $k=1$, ADZEN must remove either the middle billboard, the first two billboards, the last two billboards or the first and last billboard.

Being a for-profit company, ADZEN wants to lose as little advertising revenue as possible when removing the billboards. They want to comply with the new ordinance in such a way that the remaining billboards maximize their total revenues (i.e., the sum of  revenues generated by the billboards left standing on Main street).

Given $n$, $\boldsymbol{\mbox{k}}$, and the revenue of each of the $n$ billboards, find and print the maximum profit that ADZEN can earn while complying with the zoning ordinance. Assume that Main street is a straight, contiguous block of $n$ billboards that can be removed but cannot be reordered in any way.  

For example, if there are $n=7$ billboards, and $k=3$ is the maximum number of consecutive billboards that can be active, with $revenues=[5,6,4,2,10,8,4]$, then the maximum revenue that can be generated is $37$: $5+6+4+10+8+4=37$.  

Function Description  

Complete the billboards function in the editor below.  It should return an integer that represents the maximum revenue that can be generated under the rules.  

billboards has the following parameter(s):  

k: an integer that represents the longest contiguous group of billboards allowed  
revenue: an integer array where each element represents the revenue potential for a billboard at that index  

Input Format

The first line contains two space-separated integers, $n$ (the number of billboards) and $\boldsymbol{\mbox{k}}$ (the maximum number of billboards that can stand together on any part of the road). 

Each line $\boldsymbol{i}$ of the $n$ subsequent lines contains an integer denoting the revenue value of billboard $\boldsymbol{i}$ (where $0\leq i<n$).

Constraints

$1\leq n\leq10^5$
$1\leq k\leq n$
$0\leq\:\text{revenue value of any billboard}\:\leq2\cdot10^9$

Output Format

Print a single integer denoting the maximum profit ADZEN can earn from Main street after complying with the city's ordinance.

Sample Input 0      

6 2   
1  
2  
3  
1  
6  
10 

Sample Output 0     

21

Explanation 0 

There are $n=6$ billboards, and we must remove some of them so that no more than $k=2$ billboards are immediately next to one another.

We remove the first and fourth billboards, which gives us the configuration _ 2 3 _ 6 10 and a profit of $2+3+6+10=21$. As no other configuration has a profit greater than $21$, we print $21$ as our answer.

Sample Input 1      

5 4
1
2
3
4
5

Sample Output 1     

14

Explanation 1 

There are $n=5$ billboards, and we must remove some of them so that no more than $k=4$ billboards are immediately next to one another.

We remove the first billboard, which gives us the configuration _ 2 3 4 5 and a profit of $2+3+4+5=14$. As no other configuration has a profit greater than $\mathbf{14}$, we print $\mathbf{14}$ as our answer.

Difficulty: HARD
Tags: Dynamic programming
Skill types: Dynamic programming

Starter code:

Solutions:
NK = input().split(' ')
N = int(NK[0])
K = int(NK[1])
profits = []
for billboard in range(N):
	profits.append(int(input()))
total = sum(profits)
if K >= N:
	print(total)
elif K == 0:
	print(0)
else:
	DPtable = []
	queue = []
	for (index, profit) in enumerate(profits[:K + 1]):
		DPtable.append(profit)
		while len(queue) != 0 and profit <= profits[queue[-1]]:
			queue.pop()
		queue.append(index)
	for (index, profit) in enumerate(profits[K + 1:]):
		index = index + K + 1
		DPtable.append(DPtable[queue[0]] + profit)
		while len(queue) != 0 and DPtable[index] <= DPtable[queue[-1]]:
			queue.pop()
		while len(queue) != 0 and queue[0] <= index - K - 1:
			queue.pop(0)
		queue.append(index)
	DPtable.append(DPtable[queue[0]])
	print(total - DPtable[-1])


a = []
b = []
soln = []
in1 = []
out = []
n1 = input('')
k1 = n1.split()
n = int(k1[0])
k = int(k1[1])
lis = []
number = []
for i in range(0, n):
	d = input('')
	a.append(int(d))
	b.append(1)
	in1.append(a[i])
	out.append(0)
	number.append(0)
number[n - 1] = 1
for i in range(1, k):
	in1[n - 1 - i] = in1[n - i] + a[n - i - 1]
	number[n - i - 1] = i + 1
	out[n - 1 - i] = in1[n - i]
i = n - k - 1
while i >= 0:
	out[i] = max(out[i + 1], in1[i + 1])
	if number[i + 1] < k and in1[i + 1] > out[i + 1]:
		number[i] = number[i + 1] + 1
		in1[i] = in1[i + 1] + a[i]
	else:
		in1[i] = 0
		j = 0
		while j < k:
			in1[i] = in1[i] + a[i + j]
			j = j + 1
		number[i] = k
		sumi = a[i]
		j = 1
		while j <= k:
			if sumi + out[i + j] > in1[i]:
				in1[i] = sumi + out[i + j]
				number[i] = j
			sumi = sumi + a[i + j]
			j = j + 1
	i = i - 1
print(max(in1[0], out[0]))


NK = input().split(' ')
N = int(NK[0])
K = int(NK[1])
profits = []
for billboard in range(N):
	profits.append(int(input()))
total = sum(profits)
if K >= N:
	print(total)
elif K == 0:
	print(0)
else:
	DPtable = []
	queue = []
	for (index, profit) in enumerate(profits[:K + 1]):
		DPtable.append(profit)
		while len(queue) != 0 and profit <= profits[queue[-1]]:
			queue.pop()
		queue.append(index)
	for (index, profit) in enumerate(profits[K + 1:]):
		index = index + K + 1
		DPtable.append(DPtable[queue[0]] + profit)
		while len(queue) != 0 and DPtable[index] <= DPtable[queue[-1]]:
			queue.pop()
		while len(queue) != 0 and queue[0] <= index - K - 1:
			queue.pop(0)
		queue.append(index)
	DPtable.append(DPtable[queue[0]])
	print(total - DPtable[-1])


NK = input().split(' ')
N = int(NK[0])
K = int(NK[1])
profits = []
for billboard in range(N):
	profits.append(int(input()))
total = sum(profits)
if K >= N:
	print(total)
elif K == 0:
	print(0)
else:
	DPtable = []
	queue = []
	for (index, profit) in enumerate(profits[:K + 1]):
		DPtable.append(profit)
		while len(queue) != 0 and profit <= profits[queue[-1]]:
			queue.pop()
		queue.append(index)
	for (index, profit) in enumerate(profits[K + 1:]):
		index = index + K + 1
		DPtable.append(DPtable[queue[0]] + profit)
		while len(queue) != 0 and DPtable[index] <= DPtable[queue[-1]]:
			queue.pop()
		while len(queue) != 0 and queue[0] <= index - K - 1:
			queue.pop(0)
		queue.append(index)
	DPtable.append(DPtable[queue[0]])
	print(total - DPtable[-1])


(N, K) = [int(x) for x in input().split()]
DATA = ''
for _ in range(N):
	DATA += input() + ' '
A = [int(x) for x in DATA.split()]
from collections import deque
S = [x for x in A]
for i in range(len(A) - 1):
	S[i + 1] += S[i]
D = deque()
D.append((-1, 0))
answer = 0
DP = [0] * len(A)
for i in range(len(A)):
	while D[0][0] < i - K:
		D.popleft()
	DP[i] = S[i] + D[0][1]
	answer = max(answer, DP[i])
	now = None
	if i > 0:
		now = (i, DP[i - 1] - S[i])
	else:
		now = (i, -S[0])
	while len(D) and D[-1][1] <= now[1]:
		D.pop()
	D.append(now)
print(answer)


NK = input().split(' ')
N = int(NK[0])
K = int(NK[1])
profits = []
for billboard in range(N):
	profits.append(int(input()))
total = sum(profits)
if K >= N:
	print(total)
elif K == 0:
	print(0)
else:
	DPtable = []
	queue = []
	for (index, profit) in enumerate(profits[:K + 1]):
		DPtable.append(profit)
		while len(queue) != 0 and profit <= profits[queue[-1]]:
			queue.pop()
		queue.append(index)
	for (index, profit) in enumerate(profits[K + 1:]):
		index = index + K + 1
		DPtable.append(DPtable[queue[0]] + profit)
		while len(queue) != 0 and DPtable[index] <= DPtable[queue[-1]]:
			queue.pop()
		while len(queue) != 0 and queue[0] <= index - K - 1:
			queue.pop(0)
		queue.append(index)
	DPtable.append(DPtable[queue[0]])
	print(total - DPtable[-1])


import sys
import collections

def billboards(profits, k):
	if k == 0:
		return 0
	total = sum(profits)
	if k >= len(profits):
		return total
	cache = []
	queue = collections.deque()
	for (i, profit) in enumerate(profits):
		if i <= k:
			cache.append(profit)
			while queue and profit <= profits[queue[-1]]:
				queue.pop()
		else:
			cache.append(cache[queue[0]] + profit)
			while queue and cache[i] <= cache[queue[-1]]:
				queue.pop()
			while queue and queue[0] <= i - k - 1:
				queue.popleft()
		queue.append(i)
	return total - cache[queue[0]]
k = int(sys.stdin.readline().split(' ')[1])
profits = [int(line) for line in sys.stdin]
print(billboards(profits, k))


import sys
(N, K) = list(map(int, sys.stdin.readline().split()))
profits = [int(sys.stdin.readline()) for i in range(N)]
total = sum(profits)
if K == N:
	print(total)
else:
	x = profits[:K + 1]
	min_value = min(x)
	min_index = x.index(min_value)
	for i in range(K + 1, N):
		if i - min_index >= K:
			min_value = min(x[i - (K + 1):i + 1])
			min_index = x.index(min_value)
		x.append(min_value + profits[i])
		if x[i] < min_value:
			min_value = x[i]
			min_index = i
	print(total - min(x[N - (K + 1):]))


NK = input().split(' ')
N = int(NK[0])
K = int(NK[1])
profits = []
for billboard in range(N):
	profits.append(int(input()))
total = sum(profits)
if K >= N:
	print(total)
elif K == 0:
	print(0)
else:
	DPtable = []
	queue = []
	for (index, profit) in enumerate(profits[:K + 1]):
		DPtable.append(profit)
		while len(queue) != 0 and profit <= profits[queue[-1]]:
			queue.pop()
		queue.append(index)
	for (index, profit) in enumerate(profits[K + 1:]):
		index = index + K + 1
		DPtable.append(DPtable[queue[0]] + profit)
		while len(queue) != 0 and DPtable[index] <= DPtable[queue[-1]]:
			queue.pop()
		while len(queue) != 0 and queue[0] <= index - K - 1:
			queue.pop(0)
		queue.append(index)
	DPtable.append(DPtable[queue[0]])
	print(total - DPtable[-1])


NK = input().split(' ')
N = int(NK[0])
K = int(NK[1])
profits = []
for billboard in range(N):
	profits.append(int(input()))
total = sum(profits)
if K >= N:
	print(total)
elif K == 0:
	print(0)
else:
	DPtable = []
	queue = []
	for (index, profit) in enumerate(profits[:K + 1]):
		DPtable.append(profit)
		while len(queue) != 0 and profit <= profits[queue[-1]]:
			queue.pop()
		queue.append(index)
	for (index, profit) in enumerate(profits[K + 1:]):
		index = index + K + 1
		DPtable.append(DPtable[queue[0]] + profit)
		while len(queue) != 0 and DPtable[index] <= DPtable[queue[-1]]:
			queue.pop()
		while len(queue) != 0 and queue[0] <= index - K - 1:
			queue.pop(0)
		queue.append(index)
	DPtable.append(DPtable[queue[0]])
	print(total - DPtable[-1])


import sys
(N, K) = list(map(int, sys.stdin.readline().split()))
profits = [int(sys.stdin.readline()) for i in range(N)]
total = sum(profits)
if K == N:
	print(total)
else:
	x = profits[:K + 1]
	min_value = min(x)
	min_index = x.index(min_value)
	for i in range(K + 1, N):
		if i - min_index >= K:
			min_value = min(x[i - (K + 1):i + 1])
			min_index = x.index(min_value)
		x.append(min_value + profits[i])
		if x[i] < min_value:
			min_value = x[i]
			min_index = i
	print(total - min(x[N - (K + 1):]))


import sys
(N, K) = list(map(int, sys.stdin.readline().split()))
profits = [int(sys.stdin.readline()) for i in range(N)]
total = sum(profits)
if K == N:
	print(total)
else:
	x = profits[:K + 1]
	min_value = min(x)
	min_index = x.index(min_value)
	for i in range(K + 1, N):
		if i - min_index >= K:
			min_value = min(x[i - (K + 1):i + 1])
			min_index = x.index(min_value)
		x.append(min_value + profits[i])
		if x[i] < min_value:
			min_value = x[i]
			min_index = i
	print(total - min(x[N - (K + 1):]))


import sys
(N, K) = list(map(int, sys.stdin.readline().split()))
profits = [int(sys.stdin.readline()) for i in range(N)]
total = sum(profits)
if K == N:
	print(total)
else:
	x = profits[:K + 1]
	min_value = min(x)
	min_index = x.index(min_value)
	for i in range(K + 1, N):
		if i - min_index >= K:
			min_value = min(x[i - (K + 1):i + 1])
			min_index = x.index(min_value)
		x.append(min_value + profits[i])
		if x[i] < min_value:
			min_value = x[i]
			min_index = i
	print(total - min(x[N - (K + 1):]))


import sys
(N, K) = list(map(int, sys.stdin.readline().split()))
profits = [int(sys.stdin.readline()) for i in range(N)]
total = sum(profits)
if K == N:
	print(total)
else:
	x = profits[:K + 1]
	min_value = min(x)
	min_index = x.index(min_value)
	for i in range(K + 1, N):
		if i - min_index >= K:
			min_value = min(x[i - (K + 1):i + 1])
			min_index = x.index(min_value)
		x.append(min_value + profits[i])
		if x[i] < min_value:
			min_value = x[i]
			min_index = i
	print(total - min(x[N - (K + 1):]))


(N, K) = [int(x) for x in input().split()]
DATA = ''
for _ in range(N):
	DATA += input() + ' '
A = [int(x) for x in DATA.split()]
from collections import deque
S = [x for x in A]
for i in range(len(A) - 1):
	S[i + 1] += S[i]
D = deque()
D.append((-1, 0))
answer = 0
DP = [0] * len(A)
for i in range(len(A)):
	while D[0][0] < i - K:
		D.popleft()
	DP[i] = S[i] + D[0][1]
	answer = max(answer, DP[i])
	now = None
	if i > 0:
		now = (i, DP[i - 1] - S[i])
	else:
		now = (i, -S[0])
	while len(D) and D[-1][1] <= now[1]:
		D.pop()
	D.append(now)
print(answer)


(N, K) = [int(x) for x in input().split()]
DATA = ''
for _ in range(N):
	DATA += input() + ' '
A = [int(x) for x in DATA.split()]
from collections import deque
S = [x for x in A]
for i in range(len(A) - 1):
	S[i + 1] += S[i]
D = deque()
D.append((-1, 0))
answer = 0
DP = [0] * len(A)
for i in range(len(A)):
	while D[0][0] < i - K:
		D.popleft()
	DP[i] = S[i] + D[0][1]
	answer = max(answer, DP[i])
	now = None
	if i > 0:
		now = (i, DP[i - 1] - S[i])
	else:
		now = (i, -S[0])
	while len(D) and D[-1][1] <= now[1]:
		D.pop()
	D.append(now)
print(answer)


import sys
(N, K) = list(map(int, input().split()))
profits = [int(input()) for n in range(N)]
total = sum(profits)
if K == N:
	print(total)
else:
	x = profits[:K + 1]
	min_value = min(x)
	min_index = x.index(min_value)
	for i in range(K + 1, N):
		if i - min_index >= K:
			min_value = min(x[i - (K + 1):i + 1])
			min_index = x.index(min_value)
		x.append(min_value + profits[i])
		if x[i] < min_value:
			min_value = x[i]
			min_index = i
	print(total - min(x[N - (K + 1):]))


arr1 = [int(i) for i in input().strip().split(' ')]
(n, k) = (arr1[0], arr1[1])
arr2 = []
for i in range(n):
	arr2.append(int(input().strip()))
max_profit = sum(arr2)

def minimum_pairings(array1):
	array2 = []
	i = 0
	while i < len(array1) - 1:
		array2.append(min(array1[i], array1[i + 1]))
		i += 2
	if i == len(array1) - 1:
		array2.append(array1[-1])
	return array2

def find_minimum(arr):
	minimum_candidates = [arr]
	while len(minimum_candidates[-1]) != 1:
		minimum_candidates.append(minimum_pairings(minimum_candidates[-1]))
	return minimum_candidates

def update_minimums(tree, index):
	a = index
	for i in range(len(tree) - 1):
		if a == len(tree[i]) - 1 and a % 2 == 0:
			b = a
		else:
			b = a + 1 - 2 * (a % 2)
		tree[i + 1][a // 2] = min(tree[i][a], tree[i][b])
		a //= 2
	return tree
min_tree = []
for i in range(k + 1):
	min_tree.append(arr2[i])
min_tree = find_minimum(min_tree)
for i in range(k + 1, n):
	j = i % (k + 1)
	min_tree[0][j] = arr2[i] + min_tree[-1][0]
	update_minimums(min_tree, j)
print(max_profit - min_tree[-1][0])


import sys
(N, K) = list(map(int, sys.stdin.readline().split()))
profits = [int(sys.stdin.readline()) for i in range(N)]
total = sum(profits)
if K == N:
	print(total)
else:
	x = profits[:K + 1]
	min_value = min(x)
	min_index = x.index(min_value)
	for i in range(K + 1, N):
		if i - min_index >= K:
			min_value = min(x[i - (K + 1):i + 1])
			min_index = x.index(min_value)
		x.append(min_value + profits[i])
		if x[i] < min_value:
			min_value = x[i]
			min_index = i
	print(total - min(x[N - (K + 1):]))


(N, K) = [int(x) for x in input().split()]
DATA = ''
for _ in range(N):
	DATA += input() + ' '
A = [int(x) for x in DATA.split()]
from collections import deque
S = [x for x in A]
for i in range(len(A) - 1):
	S[i + 1] += S[i]
D = deque()
D.append((-1, 0))
answer = 0
DP = [0] * len(A)
for i in range(len(A)):
	while D[0][0] < i - K:
		D.popleft()
	DP[i] = S[i] + D[0][1]
	answer = max(answer, DP[i])
	now = None
	if i > 0:
		now = (i, DP[i - 1] - S[i])
	else:
		now = (i, -S[0])
	while len(D) and D[-1][1] <= now[1]:
		D.pop()
	D.append(now)
print(answer)


import sys
(N, K) = list(map(int, sys.stdin.readline().split()))
profits = [int(sys.stdin.readline()) for i in range(N)]
total = sum(profits)
if K == N:
	print(total)
else:
	x = profits[:K + 1]
	min_value = min(x)
	min_index = x.index(min_value)
	for i in range(K + 1, N):
		if i - min_index >= K:
			min_value = min(x[i - (K + 1):i + 1])
			min_index = x.index(min_value)
		x.append(min_value + profits[i])
		if x[i] < min_value:
			min_value = x[i]
			min_index = i
	print(total - min(x[N - (K + 1):]))


(N, K) = [int(x) for x in input().split()]
DATA = ''
for _ in range(N):
	DATA += input() + ' '
A = [int(x) for x in DATA.split()]
from collections import deque
S = [x for x in A]
for i in range(len(A) - 1):
	S[i + 1] += S[i]
D = deque()
D.append((-1, 0))
answer = 0
DP = [0] * len(A)
for i in range(len(A)):
	while D[0][0] < i - K:
		D.popleft()
	DP[i] = S[i] + D[0][1]
	answer = max(answer, DP[i])
	now = None
	if i > 0:
		now = (i, DP[i - 1] - S[i])
	else:
		now = (i, -S[0])
	while len(D) and D[-1][1] <= now[1]:
		D.pop()
	D.append(now)
print(answer)


(N, K) = [int(x) for x in input().split()]
DATA = ''
for _ in range(N):
	DATA += input() + ' '
A = [int(x) for x in DATA.split()]
from collections import deque
S = [x for x in A]
for i in range(len(A) - 1):
	S[i + 1] += S[i]
D = deque()
D.append((-1, 0))
answer = 0
DP = [0] * len(A)
for i in range(len(A)):
	while D[0][0] < i - K:
		D.popleft()
	DP[i] = S[i] + D[0][1]
	answer = max(answer, DP[i])
	now = None
	if i > 0:
		now = (i, DP[i - 1] - S[i])
	else:
		now = (i, -S[0])
	while len(D) and D[-1][1] <= now[1]:
		D.pop()
	D.append(now)
print(answer)


import sys
(N, K) = list(map(int, sys.stdin.readline().split()))
profits = [int(sys.stdin.readline()) for i in range(N)]
total = sum(profits)
if K == N:
	print(total)
else:
	x = profits[:K + 1]
	min_value = min(x)
	min_index = x.index(min_value)
	for i in range(K + 1, N):
		if i - min_index >= K:
			min_value = min(x[i - (K + 1):i + 1])
			min_index = x.index(min_value)
		x.append(min_value + profits[i])
		if x[i] < min_value:
			min_value = x[i]
			min_index = i
	print(total - min(x[N - (K + 1):]))


(n, k) = map(int, input().split())
a = []
for i in range(n):
	a.append(int(input()))
a.append(0)
dp = [-1 for i in range(n + 2)]
val = [0 for i in range(k + 1)]
val[k] = sum(a[k:])
for i in reversed(range(k)):
	val[i] = a[i] + val[i + 1]
for i in reversed(range(n - k, n + 2)):
	dp[i] = 0
for i in reversed(range(n - k)):
	ta = 999999999999
	if dp[i + 1] != dp[i + k + 2] + a[i + k + 1]:
		ta = min(dp[i + 1] + a[i], dp[i + 1])
	else:
		for j in range(i, i + k + 1):
			t = a[j] + dp[j + 1]
			if t < ta:
				ta = t
	dp[i] = ta
for i in range(k + 1):
	val[i] -= dp[i]
print(max(val))


(N, K) = [int(x) for x in input().split()]
DATA = ''
for _ in range(N):
	DATA += input() + ' '
A = [int(x) for x in DATA.split()]
from collections import deque
S = [x for x in A]
for i in range(len(A) - 1):
	S[i + 1] += S[i]
D = deque()
D.append((-1, 0))
answer = 0
DP = [0] * len(A)
for i in range(len(A)):
	while D[0][0] < i - K:
		D.popleft()
	DP[i] = S[i] + D[0][1]
	answer = max(answer, DP[i])
	now = None
	if i > 0:
		now = (i, DP[i - 1] - S[i])
	else:
		now = (i, -S[0])
	while len(D) and D[-1][1] <= now[1]:
		D.pop()
	D.append(now)
print(answer)


def f(b, index):
	return
str = input().split()
(n, k) = (int(str[0]), int(str[1]))
b = []
dp = [[0] * 2 for i in range(n)]
for i in range(n):
	b.append(int(input()))
dp[0][0] = 0
dp[0][1] = b[0]
max_index = 0
for i in range(1, n):
	dp[i][0] = max(dp[i - 1][0], dp[i - 1][1])
	if i < k:
		dp[i][1] = dp[i - 1][1] + b[i]
	else:
		s = b[i]
		dp[i][1] = b[i] + dp[i - 1][0]
		if max_index <= i - k:
			for j in range(i - 1, i - k, -1):
				s += b[j]
				if dp[i][1] < s + dp[j - 1][0]:
					max_index = j
					dp[i][1] = s + dp[j - 1][0]
		else:
			dp[i][1] = max(dp[i][1], dp[i - 1][1] + b[i])
print(max(dp[n - 1][0], dp[n - 1][1]))


(N, K) = [int(x) for x in input().split()]
DATA = ''
for _ in range(N):
	DATA += input() + ' '
A = [int(x) for x in DATA.split()]
from collections import deque
S = [x for x in A]
for i in range(len(A) - 1):
	S[i + 1] += S[i]
D = deque()
D.append((-1, 0))
answer = 0
DP = [0] * len(A)
for i in range(len(A)):
	while D[0][0] < i - K:
		D.popleft()
	DP[i] = S[i] + D[0][1]
	answer = max(answer, DP[i])
	now = None
	if i > 0:
		now = (i, DP[i - 1] - S[i])
	else:
		now = (i, -S[0])
	while len(D) and D[-1][1] <= now[1]:
		D.pop()
	D.append(now)
print(answer)


import sys
(N, K) = list(map(int, sys.stdin.readline().split()))
profits = [int(sys.stdin.readline()) for i in range(N)]
total = sum(profits)
if K == N:
	print(total)
else:
	x = profits[:K + 1]
	min_value = min(x)
	min_index = x.index(min_value)
	for i in range(K + 1, N):
		if i - min_index >= K:
			min_value = min(x[i - (K + 1):i + 1])
			min_index = x.index(min_value)
		x.append(min_value + profits[i])
		if x[i] < min_value:
			min_value = x[i]
			min_index = i
	print(total - min(x[N - (K + 1):]))


(N, K) = [int(x) for x in input().split()]
DATA = ''
for _ in range(N):
	DATA += input() + ' '
A = [int(x) for x in DATA.split()]
from collections import deque
S = [x for x in A]
for i in range(len(A) - 1):
	S[i + 1] += S[i]
D = deque()
D.append((-1, 0))
answer = 0
DP = [0] * len(A)
for i in range(len(A)):
	while D[0][0] < i - K:
		D.popleft()
	DP[i] = S[i] + D[0][1]
	answer = max(answer, DP[i])
	now = None
	if i > 0:
		now = (i, DP[i - 1] - S[i])
	else:
		now = (i, -S[0])
	while len(D) and D[-1][1] <= now[1]:
		D.pop()
	D.append(now)
print(answer)


(N, K) = [int(x) for x in input().split()]
DATA = ''
for _ in range(N):
	DATA += input() + ' '
A = [int(x) for x in DATA.split()]
from collections import deque
S = [x for x in A]
for i in range(len(A) - 1):
	S[i + 1] += S[i]
D = deque()
D.append((-1, 0))
answer = 0
DP = [0] * len(A)
for i in range(len(A)):
	while D[0][0] < i - K:
		D.popleft()
	DP[i] = S[i] + D[0][1]
	answer = max(answer, DP[i])
	now = None
	if i > 0:
		now = (i, DP[i - 1] - S[i])
	else:
		now = (i, -S[0])
	while len(D) and D[-1][1] <= now[1]:
		D.pop()
	D.append(now)
print(answer)


import sys
(n, k) = list(map(int, sys.stdin.readline().split()))
profits = [int(sys.stdin.readline()) for i in range(n)]
total = sum(profits)
if k == n:
	print(total)
else:
	x = profits[:k + 1]
	min_value = min(x)
	min_index = x.index(min_value)
	for i in range(k + 1, n):
		if i - min_index >= k:
			min_value = min(x[i - (k + 1):i + 1])
			min_index = x.index(min_value)
		x.append(min_value + profits[i])
		if x[i] < min_value:
			min_value = x[i]
			min_index = i
	print(total - min(x[n - (k + 1):]))


(N, K) = map(int, input().split())
X = [0]
for _ in range(N):
	X.append(int(input()))
nocut = [0 for i in range(N + 1)]
cut = [0 for i in range(N + 1)]
lastcut = 0
roll = 0
for i in range(1, N + 1):
	cut[i] = max(cut[i - 1], nocut[i - 1])
	if lastcut < i - K:
		roll = -1
		for j in range(0, K):
			if cut[i - K + j] > roll:
				roll = cut[i - K + j]
				lastcut = i - K + j
			roll += X[i - K + j + 1]
		nocut[i] = roll
	else:
		if cut[i - 1] > roll:
			roll = cut[i - 1]
			lastcut = i - 1
		roll += X[i]
		nocut[i] = roll
print(max(cut[N], nocut[N]))


import os
import sys
(N, K) = list(map(int, sys.stdin.readline().split()))
profits = [int(sys.stdin.readline()) for i in range(N)]
total = sum(profits)
if K == N:
	print(total)
else:
	x = profits[:K + 1]
	min_value = min(x)
	min_index = x.index(min_value)
	for i in range(K + 1, N):
		if i - min_index >= K:
			min_value = min(x[i - (K + 1):i + 1])
			min_index = x.index(min_value)
		x.append(min_value + profits[i])
		if x[i] < min_value:
			min_value = x[i]
			min_index = i
	print(total - min(x[N - (K + 1):]))


import sys
(N, K) = list(map(int, sys.stdin.readline().split()))
profits = [int(sys.stdin.readline()) for i in range(N)]
total = sum(profits)
if K == N:
	print(total)
else:
	x = profits[:K + 1]
	min_value = min(x)
	min_index = x.index(min_value)
	for i in range(K + 1, N):
		if i - min_index >= K:
			min_value = min(x[i - (K + 1):i + 1])
			min_index = x.index(min_value)
		x.append(min_value + profits[i])
		if x[i] < min_value:
			min_value = x[i]
			min_index = i
	print(total - min(x[N - (K + 1):]))


import sys

class Max_slice:

	def __init__(self, w):
		self.w = w
		self.x = []

	def add(self, i, val):
		while self.x and val >= self.x[-1][1]:
			self.x.pop()
		while self.x and self.x[0][0] <= i - self.w:
			self.x.pop(0)
		self.x.append((i, val))
		return self.x[0][1]

def billboards(line):
	(n, k) = map(int, next(line).split())
	d = [0]
	for _ in range(n):
		d.append(int(next(line)) + d[-1])
	for _ in range(k - 1):
		d.append(0)
	f = [0] * k
	(q0, q1) = (0, 0)
	r = 0
	q = Max_slice(k)
	for i in range(n, 0, -1):
		f[i % k] = d[i] + q0
		_m = q.add(n - i - 1, d[i] + q0)
		q0 = q1
		q1 = _m - d[i - 1]
		if q1 > r:
			r = q1
	print(r)
billboards(sys.stdin)


inp = input('')
con = inp.split(' ')
n = int(con[0])
k = int(con[1])
cost = []
for i in range(n):
	a = input('')
	cost.append(int(a))
sliced = cost[:k]
scam = sum(sliced)
R = [scam - i for i in sliced[::-1]] + [scam]
inter = scam
a = k + 1
b = n + 1
cumm = a
while cumm < b:
	for j in range(a, b):
		x = R.index(inter)
		if x == k:
			R.pop()
			R = [inter] + [cost[j - 1] + i for i in R]
			inter = max(R)
			cumm += 1
			a = j + 1
			break
		elif j + k - x >= b:
			chunk = cost[j - 1:]
			Sum = sum(chunk)
			R_1 = [inter + Sum - i for i in (chunk[::-1] if chunk != [] else [0])]
			R = R_1 + [Sum + i for i in R[x:x + 1 + k - len(R_1)]]
			cumm = b
			inter = max(R)
			break
		else:
			chunk = cost[j - 1:k - x + j - 1]
			Sum = sum(chunk)
			R = [inter + Sum - i for i in (chunk[::-1] if chunk != [] else [0])] + [Sum + i for i in R[:x + 1]]
			inter = max(R)
			cumm += k - x
			count = cumm
			a = j + k - x
			break
print(inter)


import sys
(N, K) = list(map(int, sys.stdin.readline().split()))
profits = [int(sys.stdin.readline()) for i in range(N)]
total = sum(profits)
if K == N:
	print(total)
else:
	x = profits[:K + 1]
	min_value = min(x)
	min_index = x.index(min_value)
	for i in range(K + 1, N):
		if i - min_index >= K:
			min_value = min(x[i - (K + 1):i + 1])
			min_index = x.index(min_value)
		x.append(min_value + profits[i])
		if x[i] < min_value:
			min_value = x[i]
			min_index = i
	print(total - min(x[N - (K + 1):]))


(N, K) = [int(x) for x in input().split()]
DATA = ''
for _ in range(N):
	DATA += input() + ' '
A = [int(x) for x in DATA.split()]
from collections import deque
S = [x for x in A]
for i in range(len(A) - 1):
	S[i + 1] += S[i]
D = deque()
D.append((-1, 0))
answer = 0
DP = [0] * len(A)
for i in range(len(A)):
	while D[0][0] < i - K:
		D.popleft()
	DP[i] = S[i] + D[0][1]
	answer = max(answer, DP[i])
	now = None
	if i > 0:
		now = (i, DP[i - 1] - S[i])
	else:
		now = (i, -S[0])
	while len(D) and D[-1][1] <= now[1]:
		D.pop()
	D.append(now)
print(answer)


import sys
(N, K) = list(map(int, sys.stdin.readline().split()))
profits = [int(sys.stdin.readline()) for i in range(N)]
total = sum(profits)
if K == N:
	print(total)
else:
	x = profits[:K + 1]
	min_value = min(x)
	min_index = x.index(min_value)
	for i in range(K + 1, N):
		if i - min_index >= K:
			min_value = min(x[i - (K + 1):i + 1])
			min_index = x.index(min_value)
		x.append(min_value + profits[i])
		if x[i] < min_value:
			min_value = x[i]
			min_index = i
	print(total - min(x[N - (K + 1):]))


import math
import os
import random
import re
import sys
a = []
b = []
soln = []
in1 = []
out = []
n1 = input('')
k1 = n1.split()
n = int(k1[0])
k = int(k1[1])
lis = []
number = []
for i in range(0, n):
	d = input('')
	a.append(int(d))
	b.append(1)
	in1.append(a[i])
	out.append(0)
	number.append(0)
number[n - 1] = 1
for i in range(1, k):
	in1[n - 1 - i] = in1[n - i] + a[n - i - 1]
	number[n - i - 1] = i + 1
	out[n - 1 - i] = in1[n - i]
i = n - k - 1
while i >= 0:
	out[i] = max(out[i + 1], in1[i + 1])
	if number[i + 1] < k and in1[i + 1] > out[i + 1]:
		number[i] = number[i + 1] + 1
		in1[i] = in1[i + 1] + a[i]
	else:
		in1[i] = 0
		j = 0
		while j < k:
			in1[i] = in1[i] + a[i + j]
			j = j + 1
		number[i] = k
		sumi = a[i]
		j = 1
		while j <= k:
			if sumi + out[i + j] > in1[i]:
				in1[i] = sumi + out[i + j]
				number[i] = j
			sumi = sumi + a[i + j]
			j = j + 1
	i = i - 1
print(max(in1[0], out[0]))


a = []
b = []
soln = []
in1 = []
out = []
n1 = input('')
k1 = n1.split()
n = int(k1[0])
k = int(k1[1])
lis = []
number = []
for i in range(0, n):
	d = input('')
	a.append(int(d))
	b.append(1)
	in1.append(a[i])
	out.append(0)
	number.append(0)
number[n - 1] = 1
for i in range(1, k):
	in1[n - 1 - i] = in1[n - i] + a[n - i - 1]
	number[n - i - 1] = i + 1
	out[n - 1 - i] = in1[n - i]
i = n - k - 1
while i >= 0:
	out[i] = max(out[i + 1], in1[i + 1])
	if number[i + 1] < k and in1[i + 1] > out[i + 1]:
		number[i] = number[i + 1] + 1
		in1[i] = in1[i + 1] + a[i]
	else:
		in1[i] = 0
		j = 0
		while j < k:
			in1[i] = in1[i] + a[i + j]
			j = j + 1
		number[i] = k
		sumi = a[i]
		j = 1
		while j <= k:
			if sumi + out[i + j] > in1[i]:
				in1[i] = sumi + out[i + j]
				number[i] = j
			sumi = sumi + a[i + j]
			j = j + 1
	i = i - 1
print(max(in1[0], out[0]))


a = []
b = []
soln = []
in1 = []
out = []
n1 = input('')
k1 = n1.split()
n = int(k1[0])
k = int(k1[1])
lis = []
number = []
for i in range(0, n):
	d = input('')
	a.append(int(d))
	b.append(1)
	in1.append(a[i])
	out.append(0)
	number.append(0)
number[n - 1] = 1
for i in range(1, k):
	in1[n - 1 - i] = in1[n - i] + a[n - i - 1]
	number[n - i - 1] = i + 1
	out[n - 1 - i] = in1[n - i]
i = n - k - 1
while i >= 0:
	out[i] = max(out[i + 1], in1[i + 1])
	if number[i + 1] < k and in1[i + 1] > out[i + 1]:
		number[i] = number[i + 1] + 1
		in1[i] = in1[i + 1] + a[i]
	else:
		in1[i] = 0
		j = 0
		while j < k:
			in1[i] = in1[i] + a[i + j]
			j = j + 1
		number[i] = k
		sumi = a[i]
		j = 1
		while j <= k:
			if sumi + out[i + j] > in1[i]:
				in1[i] = sumi + out[i + j]
				number[i] = j
			sumi = sumi + a[i + j]
			j = j + 1
	i = i - 1
print(max(in1[0], out[0]))


a = []
b = []
soln = []
in1 = []
out = []
n1 = input('')
k1 = n1.split()
n = int(k1[0])
k = int(k1[1])
lis = []
number = []
for i in range(0, n):
	d = input('')
	a.append(int(d))
	b.append(1)
	in1.append(a[i])
	out.append(0)
	number.append(0)
number[n - 1] = 1
for i in range(1, k):
	in1[n - 1 - i] = in1[n - i] + a[n - i - 1]
	number[n - i - 1] = i + 1
	out[n - 1 - i] = in1[n - i]
i = n - k - 1
while i >= 0:
	out[i] = max(out[i + 1], in1[i + 1])
	if number[i + 1] < k and in1[i + 1] > out[i + 1]:
		number[i] = number[i + 1] + 1
		in1[i] = in1[i + 1] + a[i]
	else:
		in1[i] = 0
		j = 0
		while j < k:
			in1[i] = in1[i] + a[i + j]
			j = j + 1
		number[i] = k
		sumi = a[i]
		j = 1
		while j <= k:
			if sumi + out[i + j] > in1[i]:
				in1[i] = sumi + out[i + j]
				number[i] = j
			sumi = sumi + a[i + j]
			j = j + 1
	i = i - 1
print(max(in1[0], out[0]))


a = []
b = []
soln = []
in1 = []
out = []
n1 = input('')
k1 = n1.split()
n = int(k1[0])
k = int(k1[1])
lis = []
number = []
for i in range(0, n):
	d = input('')
	a.append(int(d))
	b.append(1)
	in1.append(a[i])
	out.append(0)
	number.append(0)
number[n - 1] = 1
for i in range(1, k):
	in1[n - 1 - i] = in1[n - i] + a[n - i - 1]
	number[n - i - 1] = i + 1
	out[n - 1 - i] = in1[n - i]
i = n - k - 1
while i >= 0:
	out[i] = max(out[i + 1], in1[i + 1])
	if number[i + 1] < k and in1[i + 1] > out[i + 1]:
		number[i] = number[i + 1] + 1
		in1[i] = in1[i + 1] + a[i]
	else:
		in1[i] = 0
		j = 0
		while j < k:
			in1[i] = in1[i] + a[i + j]
			j = j + 1
		number[i] = k
		sumi = a[i]
		j = 1
		while j <= k:
			if sumi + out[i + j] > in1[i]:
				in1[i] = sumi + out[i + j]
				number[i] = j
			sumi = sumi + a[i + j]
			j = j + 1
	i = i - 1
print(max(in1[0], out[0]))


a = []
b = []
soln = []
in1 = []
out = []
n1 = input('')
k1 = n1.split()
n = int(k1[0])
k = int(k1[1])
lis = []
number = []
for i in range(0, n):
	d = input('')
	a.append(int(d))
	b.append(1)
	in1.append(a[i])
	out.append(0)
	number.append(0)
number[n - 1] = 1
for i in range(1, k):
	in1[n - 1 - i] = in1[n - i] + a[n - i - 1]
	number[n - i - 1] = i + 1
	out[n - 1 - i] = in1[n - i]
i = n - k - 1
while i >= 0:
	out[i] = max(out[i + 1], in1[i + 1])
	if number[i + 1] < k and in1[i + 1] > out[i + 1]:
		number[i] = number[i + 1] + 1
		in1[i] = in1[i + 1] + a[i]
	else:
		in1[i] = 0
		j = 0
		while j < k:
			in1[i] = in1[i] + a[i + j]
			j = j + 1
		number[i] = k
		sumi = a[i]
		j = 1
		while j <= k:
			if sumi + out[i + j] > in1[i]:
				in1[i] = sumi + out[i + j]
				number[i] = j
			sumi = sumi + a[i + j]
			j = j + 1
	i = i - 1
print(max(in1[0], out[0]))