Read problems statements in Mandarin Chinese  and Russian. 
The Baratheons have been ruling in the Seven Kingdoms for many years. They have seen a lot: prosperity and hunger, tranquility and rebellions, live and death. But nevertheless, they still hold the throne.

King Joffrey Baratheon's reign is running now. As a wise man, he honors the history of his family. So, he commanded to build up two monuments, that will remind about some historical periods of the Baratheons.

Formally, the Baratheons have been ruling for N years. Every year is described by an integer A_{i}, the level of prosperity in i-th year. If i-th year was a great year, then A_{i} might be a positive integer. Otherwise, if i-th year was a horrible year, then A_{i} might be a negative integer.

Each historical period can be described as two integers S and F, the start and the finish of the period respectively. Of course, S is not greater than F for each period, that we consider in this task.

You are to pick two historical periods, but there are some rules:

Two periods shouldn't have common years. I.e. a period [1, 5] has no common years with a period [6, 7];
The first period should start earlier than the second one. I.e. a period [1, 5] starts earlier than [6, 7];
Two periods shouldn't be too close to each other. There must be at least K years between the finish of the first period and the start of the second period. I.e. periods [1, 5] and [10, 10] can be chosen in case K equals to 4, while they can't in case K equals to 5.
The sum of the levels of prosperity in chosen years should be as big as possible.

Afterwards, you should report the sum of the levels of prosperity in chosen years to your King. Make everything right, otherwise King Joffrey won't be merciful!

------ Input ------ 

The first line of the input contains an integer T denoting the number of test cases. The description of T test cases follows.

The first line of each test case contains two integers N and K denoting the length of the Baratheons' reign and the minimal amount of years between two chosen periods.

The second line contains N space-separated integers A_{1}, A_{2}, ..., A_{N} denoting the levels of prosperity in corresponding years.
 
------ Output ------ 

For each test case, output a single line containing the required integer.
 
------ Constraints ------ 

$1 ≤ T ≤ 5;$
$2 ≤ N ≤ 10^{5};$
$0 ≤ K ≤ 10^{5};$
$-10^{9} ≤ A_{i} ≤ 10^{9} for every 1 ≤ i ≤ N;$
$K + 2 ≤ N$
 
----- Sample Input 1 ------ 
3
5 3
-1 1 2 3 -1
8 3
5 5 -1 -2 3 -1 2 -2
6 0
5 -1 5 0 -1 9
----- Sample Output 1 ------ 
-2
12
18
----- explanation 1 ------ 
There are T = 3 test cases the input.
The first test case: N equals to 5, K equals to 3, A[] equals to {-1, 1, 2, 3, -1}. There is the only option: we have to choose [1, 1] and [5, 5] periods.
The second test case: N equals to 8, K equals to 3, A[] equals to {5, 5, -1, -2, 3, -1, 2, -2}. It is optimal to choose [1, 2] and [7, 7] periods. That is the only optimal choice that you can make.
The second test case: N equals to 6, K equals to 0, A[] equals to {5, -1, 5, 0, -1, 9}. It is optimal to choose [1, 3] and [6, 6] periods. But that is not the only optimal choice that you can make.

Difficulty: MEDIUM_HARD
Tags: Dynamic programming
Skill types: Dynamic programming

Starter code:

Solutions:
def reign(arr, K):
	subarr1 = kadanesmax(arr)
	arr.reverse()
	subarr2 = kadanesmax(arr)
	subarr2.reverse()
	prosperity = arr[0] + arr[-1]
	for i in range(len(arr) - K - 1):
		year = subarr2[i + (K + 1)] + subarr1[i]
		prosperity = max(prosperity, year)
	return prosperity

def kadanesmax(arr):
	maxend = arr[0]
	maxupto = arr[0]
	lmax = [arr[0]]
	for i in range(1, len(arr)):
		if maxend < 0:
			maxend = arr[i]
		else:
			maxend += arr[i]
		maxupto = max(maxupto, maxend)
		lmax.append(maxupto)
	return lmax
T = int(input())
for t in range(T):
	constraint = input()
	(N, K) = [int(x) for x in constraint.split()]
	line = input()
	years = [int(x) for x in line.split()]
	print(reign(years, K))


t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	L = list(map(int, input().split()))
	M = [L[0]]
	for i in range(1, n):
		M.append(max(0, M[-1]) + L[i])
	N = [L[-1]]
	for i in range(n - 2, -1, -1):
		N.append(max(0, N[-1]) + L[i])
	M1 = [M[0]]
	m = M[0]
	for i in range(1, n):
		m = max(m, M[i])
		M1.append(m)
	N1 = [N[0]]
	m = N[0]
	for i in range(1, n):
		m = max(m, N[i])
		N1.append(m)
	N1.reverse()
	i = 0
	j = k + 1
	ans = M1[i] + N1[j]
	while j < n:
		ans = max(ans, M1[i] + N1[j])
		i += 1
		j += 1
	print(ans)


import math

def snek(a, n, k):
	ans = [-math.inf] * (n - k)
	c = 0
	for x in range(n - k):
		c += a[x]
		if c < a[x]:
			c = a[x]
		ans[x] = max(c, ans[x - 1])
	return ans
t = int(input())
for i in range(t):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	k += 1
	l = snek(a, n, k)
	r = snek(a[::-1], n, k)[::-1]
	ans = -math.inf
	for j in range(n - k):
		m = l[j] + r[j]
		if m > ans:
			ans = m
	print(ans)


t = int(input())
for i in range(t):
	(n, k) = input().split(' ')
	n = int(n)
	k = int(k)
	arr = input().split(' ')
	arr = [int(x) for x in arr[:n]]
	lpsum = [0 for i in range(n)]
	rpsum = [0 for i in range(n)]
	lpsum[0] = arr[0]
	rpsum[-1] = arr[-1]
	for i in range(1, n):
		if arr[i] >= arr[i] + lpsum[i - 1]:
			lpsum[i] = arr[i]
		else:
			lpsum[i] = arr[i] + lpsum[i - 1]
	for i in range(n - 2, -1, -1):
		if arr[i] >= rpsum[i + 1] + arr[i]:
			rpsum[i] = arr[i]
		else:
			rpsum[i] = arr[i] + rpsum[i + 1]
	lmax = [0 for i in range(n)]
	rmax = [0 for i in range(n)]
	lmaxi = -float('inf')
	for i in range(n):
		lmax[i] = max(lmaxi, lpsum[i])
		lmaxi = max(lmaxi, lpsum[i])
	rmaxi = -float('inf')
	for i in range(n - 1, -1, -1):
		rmax[i] = max(rmaxi, rpsum[i])
		rmaxi = max(rmaxi, rpsum[i])
	ans = -float('inf')
	for i in range(0, n - k - 1):
		ans = max(ans, lmax[i] + rmax[i + k + 1])
	print(ans)


import math

def helper(arr, n, k):
	ans = [-math.inf] * (n - k)
	cur = 0
	for x in range(n - k):
		cur += arr[x]
		if cur < arr[x]:
			cur = arr[x]
		ans[x] = max(cur, ans[x - 1])
	return ans
t = int(input())
for x in range(t):
	(n, k) = map(int, input().split())
	arr = list(map(int, input().split()))
	k += 1
	left = helper(arr, n, k)
	right = helper(arr[::-1], n, k)[::-1]
	ans = -math.inf
	for x in range(n - k):
		temp = left[x] + right[x]
		if temp > ans:
			ans = temp
	print(ans)


import sys

def solveCase():
	global tabInit, K, tab, tabR2L
	(N, K) = map(int, f.readline().split())
	tabInit = list(map(int, f.readline().split()))
	tab = [v for v in tabInit]
	tabR2L = [v for v in tabInit]
	for i in range(1, N):
		s = tab[i - 1] + tab[i]
		if s > tab[i]:
			tab[i] = s
	for i in range(1, N):
		if tab[i - 1] > tab[i]:
			tab[i] = tab[i - 1]
	for i in range(N - 2, -1, -1):
		s = tabR2L[i + 1] + tabR2L[i]
		if s > tabR2L[i]:
			tabR2L[i] = s
	for i in range(N - 2, -1, -1):
		if tabR2L[i + 1] > tabR2L[i]:
			tabR2L[i] = tabR2L[i + 1]
	valMax = -sys.maxsize
	for i in range(0, N - K - 1):
		valMax = max(valMax, tab[i] + tabR2L[i + K + 1])
	return valMax

def tests():
	global f
	f = open('tests.txt')
	bFail = False
	i = 1
	while 'END' not in f.readline():
		res = str(solveCase())
		resExp = f.readline()[:-1]
		if res != resExp:
			print('------>  TEST', i, 'FAILED !' + ' Found :', res, ', Expected :', resExp)
			print(K, tabInit)
			print(tab)
			print(tabR2L)
			bFail = True
		else:
			print('TEST', i, 'PASSED', ' Found :', res, ', Expected :', resExp)
		i += 1
	if not bFail:
		print('\n--- ALL OF THE ' + str(i - 1) + ' TESTS HAVE SUCCEEDED ---')

def main():
	global f
	i = 0
	if i == 1:
		tests()
		return
	f = sys.stdin
	n = int(input())
	for _ in range(n):
		print(solveCase())
main()


def SolveInc(z):
	MemInc[len(A) - 1] = A[len(A) - 1]
	for i in range(len(A) - 2, -1, -1):
		MemInc[i] = max(A[i], A[i] + MemInc[i + 1])
	return

def SolveDec(z):
	MemDec[0] = A[0]
	for i in range(1, len(A)):
		MemDec[i] = max(A[i], A[i] + MemDec[i - 1])
	return
T = int(input())
MemInc = []
MemDec = []
for t in range(T):
	(N, k) = map(int, input().split())
	MemInc = []
	MemDec = []
	for i in range(N):
		MemInc.append('s')
		MemDec.append('s')
	A = list(map(int, input().split()))
	x = SolveInc(0)
	x = SolveDec(N - 1)
	for i in range(N - 2, -1, -1):
		if MemInc[i] < MemInc[i + 1]:
			MemInc[i] = MemInc[i + 1]
	for i in range(1, N):
		if MemDec[i] < MemDec[i - 1]:
			MemDec[i] = MemDec[i - 1]
	maxx = 0
	for start in range(1, len(A) - k):
		x = MemDec[start - 1] + MemInc[start + k]
		if x > maxx or start == 1:
			maxx = x
	print(maxx)