once-upon-a-time-in-time-land

In a mystical TimeLand, a person's health and wealth is measured in terms of time(seconds) left. 
Suppose a person there has 24x60x60 = 86400 seconds left, then he would live for another 1 day.
A person dies when his time left becomes 0. Some time-amount can be borrowed from other person, or time-banks.
Some time-amount can also be lend to another person, or can be used to buy stuffs.

Our hero Mr X, is in critical condition, has very less time left.

Today's the inaugural day of a new time-bank. So they are giving away free time-amount worth 1000 years. 

Bank released N slips, A[1], A[2], .... A[N]. Each slip has a time-amount(can be +ve as well as -ve). 

A person can pick any number of slips(even none, or all of them, or some of them) out of the N slips.
But bank introduced a restriction, they announced one more number K. Restriction is that, 
if a person picks a slip A[i], then the next slip that he can choose to pick will be A[i+K+1]. 
It means there should be a difference of atleast K between the indices of slips picked.

Now slip(s) should be picked in such a way that their sum results in maximum positive time-amount sum possible with the given restriction.

If you predict the maximum positive sum possible, then you win.

Mr X has asked for your help. Help him win the lottery, and make it quick!

Input Format:
First line of the test file contains single number T, the number of test cases to follow.
Each test case consists of two lines.First line contains two numbers N and K , separated by a space.
Second line contains the N numbers A[1], A[2] ..... A[N] separated by space.

Output Format:
For every test case, output in a single line the maximum positive sum possible, that is output for the case.

Constraints:
T ≤ 250
N ≤ 10000
-10^9 ≤ A[i] ≤ 10^9
0 ≤ K ≤ N-1

SAMPLE INPUT
2
10 1
1 2 -3 -5 4 6 -3 2 -1 2
10 2
1 2 -3 -5 4 6 -3 2 -1 2

SAMPLE OUTPUT
12
10

Explanation

1st Case:
We can take slips { A[2]=2, A[6]=6, A[8]=2, A[10]=2 }, slips are atleast 1 indices apart
this makes maximum sum, A[2]+A[6]+A[8]+A[10]=12

2nd Case:
We can take slips { A[2]=2, A[6]=6, A[10]=2 }, slips are atleast 2 indices apart
this makes maximum sum, A[2]+A[6]+A[10]=10

Difficulty: EASY
Tags: Dynamic programming
Skill types: Dynamic programming

Starter code:

Solutions:
t=eval(input())
while t:
	(n,k)=list(map(int,input().split()))
	a=list(map(int,input().split()))
	flag=1
	for i in range(n):
		if a[i]>0:
			flag=0
	if flag:
		print(0)
	else:
		dp=[0]*n
		dp[0]=max(0,a[0])
		for i in range(1,k+1):
				dp[i]=max(a[i],dp[i-1])
		for i in range(k+1,n):
			dp[i]=max(dp[i-1],dp[i-(k+1)]+a[i])
		print(dp[n-1])
	t-=1


def all_max(arr):
	sum1 = 0
	for i in arr:
		if i > 0:
			sum1 += i
	return sum1

if __name__=='__main__':
	T = int(input())
	for _ in range(T):
		n,k=list(map(int,input().split()))
		arr = list(map(int,input().split()))
		result=0
		memo = [0]*n
		if k==0:
			print((all_max(arr)))
		else:
			for i in range(n):
				if i == 0:
					if arr[i] > 0:
						memo[i]=arr[i]
				else:
					if i > k:
						result = max(memo[i-1],arr[i]+memo[i-k-1])
						memo[i]=result
					else:
						result = max(arr[i],memo[i-1])
						memo[i] = result
			if result < 0:
				print(0)
			else:
				print(result)
		   # print("memo")
		   # print(memo)


_ = int(input())
for __ in range (_):
	N,K=list(map(int,input().split()))
	ARR = list(map(int,input().split()))
	ANS = []
	ANS.append(max(0,ARR[0]))
	for i in range(1,K+1):
		ANS.append(max(ANS[i-1],ARR[i]))

	for i in range(K+1,N):
		ANS.append(max(ANS[i-1],ANS[i-K-1]+ARR[i]))

	print(ANS[N-1])


t=eval(input())
for tt in range(0,t):
	s=input()
	ds=s.split(" ")
	n=int(ds[0])
	k=int(ds[1])
	#print k
	s_data = list(map(int, input().split()))
	i_len=n
	i_data=[]
	ans=0
	for i in range(0,i_len):
		if i-k<=0:
			if ans<s_data[i]:
				ans=s_data[i]
				i_data.append(ans)
			else:
				i_data.append(ans)
		else:
			if s_data[i]>(i_data[i-k-1]+s_data[i]):
				if ans>s_data[i]:
					i_data.append(ans)
				else:
					i_data.append(s_data[i])
					ans=i_data[i]
			else:
				if ans>(i_data[i-k-1]+s_data[i]):
					i_data.append(ans);
				else:
					i_data.append(i_data[i-k-1]+s_data[i])
					ans=(i_data[i-k-1]+s_data[i])
	print(ans)


t = int(input())
while t>0:
	n,k = list(map(int,input().split()))
	arr = list(map(int,input().split()))
	max_d = [0]*n
	for i in range(n-1,-1,-1):
		if arr[i] > 0:
			if i+k+1 < n:
				max_d[i] = max(arr[i] + max_d[i+k+1],max_d[i+1])
			else:
				if i+1 < n:
					max_d[i] = max(arr[i],max_d[i+1])
				else:
					max_d[i] = arr[i]
		else:
			if i+1 < n:
				max_d[i] = max_d[i+1]
			else:
				max_d[i] = 0
	print(max_d[0])
	t-=1


_ = eval(input())

for __ in range (_):
	n,k = list(map(int,input().split()))
	arr = list(map(int, input().split()))	
	ans = []	
	ans.append(max(0,arr[0]))	
	for i in range (1,k+1):
		ans.append(max(ans[i-1],arr[i]))	
	for i in range (k+1,n):
		ans.append(max(ans[i-1],ans[i-k-1]+arr[i]))		
	print(ans[n-1])


test = int(input())
while test > 0:
	dp = []
	test -= 1
	N, K = list(map(int, input().split()))
	A = list(map(int, input().split()))
	for i in range(0, min(1 + K, N)):
		if len(dp) == 0:
			dp.append(A[i])
		else:
			dp.append(max(dp[-1], A[i]))

	for i in range(1 + K, N):
		dp.append(max(dp[i - K - 1] + A[i], A[i], dp[i - K - 1], dp[-1]))
	print(max(max(dp), 0))
	#print dp




'''input
2
10 1
1 2 -3 -5 4 6 -3 2 -1 2
10 2
1 2 -3 -5 4 6 -3 2 -1 2
'''

def kadane(nlist):
	r = 0
	for mem in nlist:
		if mem  < 0:
			pass
		else:
			r = mem+r
	return r

t = int(input())
for test in range(t):
	n,k = list(map(int,input().split()))
	nlist = [ int(x) for x in input().split() ]
	res = 0
	reslist = [0]*len(nlist)
	if k ==0:
		print(kadane(nlist))
	else:
		for r1 in range(len(nlist)):
			if r1 == 0:
				if nlist[r1] > 0:
					reslist[r1] = nlist[r1]
			else:
				if r1 > k:
					res = max(reslist[r1-1],nlist[r1] + reslist[r1-k-1])
					reslist[r1] = res
					#print "Reslist2-->",reslist
				else:
					res = max(nlist[r1],reslist[r1-1])
					reslist[r1] = res
					#print "Reslist3-->",reslist
		if res < 0:
			print(0)
		else:
			print(res)


__author__ = 'apritam'


def getMax(data,range):
	if range==0:
		result = 0
		for d in data:
			if d > 0:
				result = result+d
		return result
	elif data.__len__()==range+1:
		max=0
		for d in data:
			if d>max:
				max = d
		return max
	else:
		max_a=[]
		index = 0
		while index<data.__len__():
			if index == 0:
				if(data[0]>0):
					max_a.append(data[0])
				else:
					max_a.append(0)
				index+=1
				continue
			if(index<=range):
				if max_a[max_a.__len__()-1]<data[index]:
					max_a.append(data[index])
				else:
					max_a.append(max_a[max_a.__len__()-1])
				index+=1
				continue
			if(data[index]+max_a[max_a.__len__()-1-range]>max_a[max_a.__len__()-1]):
				max_a.append(data[index]+max_a[max_a.__len__()-1-range])
			else:
				max_a.append(max_a[max_a.__len__()-1])
			index+=1
		return max_a[max_a.__len__()-1]



no_of_test=int(input())
while no_of_test > 0:
	t_range = input().split(' ')
	t= int(t_range[0])
	range = int(t_range[1])
	data_str=input().split(' ')
	data =[];
	for d in data_str:
		if d.__len__()>0:
			data.append(int(d))
	if(data.__len__()>0):
		print(getMax(data,range))
	else:
		print(0)

	no_of_test-=1


t = int(input())
while t:
	t=t-1
	n,k = list(map(int,input().split()))
	a = list(map(int,input().split()))
	r = [0]*(n)
	for i in range(n):
		if i==0:
			r[i]=max(0,a[i])
		elif i<(k+1):
			r[i] = 	max(r[i-1],a[i])
		else:
			r[i] = max(r[i-1],a[i]+r[i-k-1])
	print(r[n-1])


t = int(input())
while t:
	t=t-1
	n,k = list(map(int,input().split()))
	a = list(map(int,input().split()))
	r = [0]*(n)
	for i in range(n):
		if i==0:
			r[i]=max(0,a[i])
		elif i<(k+1):
			r[i] = 	max(r[i-1],a[i])
		else:
			r[i] = max(r[i-1],a[i]+r[i-k-1])
	print(r[n-1])


T=int(input())

while T>0:
	N,K=[int(x) for x in input().split()[:2]]
	tList=[int(x) for x in input().split()[:N]]

	if K>=N:
		print(max(max(tList),0))

	DP=[0]*(N+1)

	for x in range(0,N):

		if x>K:
			DP[x]=max(DP[x-K-1]+tList[x],DP[x-1])
		else:
			DP[x]=max(DP[x-1],tList[x])

	print(DP[N-1])
	T-=1







'''
# Read input from stdin and provide input before running code

name = raw_input('What is your name?\n')
print 'Hi, %s.' % name

'''
test_cases = eval(input())
for i in range(test_cases):
	n,k = list(map(int,input().split()))
	input1 = list(map(int,input().split()))
	a = [0 for i in range(n)]
	for i in range(n-1,-1,-1):
		try:
			g = a[i+1]
		except:
			g = 0
		try:
			m = a[i+k+1]
		except:
			m = 0
		a[i] = max(g,m+input1[i])
		
	print(a[0])


def ankit(nlist):
	r = 0
	for mem in nlist:
		if mem  < 0:
			pass
		else:
			r = mem+r
	return r
 
t = int(input())
for test in range(t):
	n,k = list(map(int,input().split()))
	nlist = [ int(x) for x in input().split() ]
	res = 0
	reslist = [0]*len(nlist)
	if k ==0:
		print(ankit(nlist))
	else:
		for r1 in range(len(nlist)):
			if r1 == 0:
				if nlist[r1] > 0:
					reslist[r1] = nlist[r1]
			else:
				if r1 > k:
					res = max(reslist[r1-1],nlist[r1] + reslist[r1-k-1])
					reslist[r1] = res
					#print "Reslist2-->",reslist
				else:
					res = max(nlist[r1],reslist[r1-1])
					reslist[r1] = res
					#print "Reslist3-->",reslist
		if res < 0:
			print(0)
		else:
			print(res)


def solve():
	n,k=[int(x) for x in input().split()]
	nums =[0]
	nums.extend( [int(x) for x in input().split()])
	
	for i in range(1,1+k+1):
		nums[i] = max(nums[i-1],nums[i])
		
	for i in range(1+k+1,n+1):
		nums[i] = max(nums[i-1],nums[i-k-1]+nums[i])
		
	print(nums[n])
	

def main():
	for _ in range(eval(input())):
		solve()
		
main()


test=int(input())
for i in  range(test):
	num,k=list(map(int,input().split()))
	lst=[]
	lst=list(map(int,input().split()))
	stack=[0 for j in range(k+1)]
	for j in range(num):
		if stack[-1]<(lst[j]+stack[0]):
			stack.append(lst[j]+stack[0])
		else:stack.append(stack[-1])
		stack.pop(0)
#		print stack
	print(stack[-1])