Read problems statements [Mandarin] , [Bengali] , [Hindi] , [Russian] and [Vietnamese] as well.

Chef is participating in a pogo stick race. In this competition, there are $N$ squares (numbered $1$ through $N$) in a row. Chef must choose a starting square, enter this square and start jumping on his pogo stick. In each jump, if Chef is at a square $s$, then he can only jump to the square $s+K$. If square $s+K$ does not exist, Chef jumps out of the row of squares and the race ends for him. It is not allowed to stop jumping any earlier.

Each square has a value; let's denote the value of the $i$-th square by $A_{i}$. Initially, Chef has $0$ points. When he jumps in some square (including the initial square), he is awarded a number of points equal to the value of this square, exactly once. Note that if this value is negative, the number of Chef's points is decreased.

Determine the maximum possible total number of points Chef can get if he selects the initial cell optimally.

------  Input ------
The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.
The first line of each test case contains two space-separated integers $N$ and $K$.
The second line contains $N$ space-separated integers $A_{1}, A_{2}, \ldots, A_{N}$.

------  Output ------
For each test case, print a single line containing one integer ― the maximum number of points.

------  Constraints  ------
$1 ≤ T ≤ 1,000$
$1 ≤ N ≤ 10^{5}$
$1 ≤ K ≤ 10^{5}$
$|A_{i}| ≤ 10,000$ for each valid $i$
the sum of $N$ over all test cases does not exceed $10^{6}$

------  Subtasks ------
Subtask #1 (30 points):
$N ≤ 1,000$
the sum of $N$ over all test cases does not exceed $10,000$

Subtask #2 (70 points): original constraints

----- Sample Input 1 ------ 
2
5 2
3 6 4 7 2
5 3
3 -5 6 3 10
----- Sample Output 1 ------ 
13
10

Difficulty: MEDIUM_HARD
Tags: Dynamic programming

Data structures
Skill types: Dynamic programming

Data structures

Starter code:

Solutions:
for t in range(int(input())):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	for i in range(k, n):
		a[i] = max(a[i], a[i] + a[i - k])
	ans = -100000
	for i in range(n - k, n):
		ans = max(ans, a[i])
	print(ans)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	arr = list(map(int, input().split()))
	max_dist = -100000
	for i in range(k):
		j = i
		sm = 0
		while j < n:
			sm += arr[j]
			if sm < arr[j]:
				sm = arr[j]
			j = j + k
		max_dist = max(sm, max_dist)
	print(max_dist)


for _ in range(int(input())):
	(N, K) = list(map(int, input().split()))
	A = list(map(int, input().split()))
	if K >= N:
		print(max(A))
		continue
	dp = [0] * (N - K) + A[-K:]
	curmax = max(A[-K:])
	for i in range(N - K - 1, -1, -1):
		dp[i] = dp[i + K] + A[i]
		if dp[i] > curmax:
			curmax = dp[i]
	print(curmax)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	A = list(map(int, input().split()))
	sums = [0] * n
	for i in range(n - 1, -1, -1):
		if i + k < n:
			sums[i] = A[i] + sums[i + k]
		else:
			sums[i] = A[i]
	print(max(sums))


t = int(input())
for u in range(t):
	(length, k) = map(int, input().split())
	arr = list(map(int, input().split()))
	if k > length:
		print(max(arr))
	else:
		dp = [-1000000000 for i in range(length)]
		for i in range(length):
			if i - k >= 0:
				dp[i] = max(0, dp[i - k]) + arr[i]
			else:
				dp[i] = arr[i]
		ans = -100000000
		for i in range(1, k + 1):
			ans = max(ans, dp[-i])
		print(ans)


t = int(input())
while t > 0:
	t -= 1
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	max_v = -100000
	for i in range(k):
		j = i
		sm = 0
		while j < n:
			sm += a[j]
			if sm < a[j]:
				sm = a[j]
			j = j + k
		max_v = max(max_v, sm)
	print(max_v)


t = int(input())
for i in range(t):
	(n, k) = map(int, input().split())
	l = list(map(int, input().split()))
	d = [0] * n
	for j in range(k):
		for z in range(n - j - 1, -1, -k):
			if z + k >= n:
				d[z] = l[z]
			else:
				d[z] = l[z] + d[z + k]
	print(max(d))


import math
t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	arr = list(map(int, input().split()))
	d = [0] * n
	for i in range(k):
		for j in range(n - i - 1, -1, -k):
			if j + k >= n:
				d[j] = arr[j]
			else:
				d[j] = arr[j] + d[j + k]
	print(max(d))


t = int(input())
for q in range(t):
	(n, k) = map(int, input().split())
	s = [0] * k
	u = []
	arr = list(map(int, input().split()))
	v = max(arr)
	for i in range(n):
		temp = i % k
		s[temp] += arr[i]
	v = max(s)
	for i in range(n - k):
		temp = i % k
		s[temp] -= arr[i]
		if s[temp] > v:
			v = s[temp]
	print(v)


t = int(input())
while t:
	(n, k) = map(int, input().split(' '))
	ls = [int(i) for i in input().split(' ')]
	ans = [[0, 0]] * k
	for i in range(n):
		ans[i % k] = [ans[i % k][0] + ls[i], ans[i % k][1] + 1]
	mVal = max(ans, key=lambda x: x[0])[0]
	for i in range(n):
		if ans[i % k][1] - 1 > 0:
			ans[i % k][0] -= ls[i]
			ans[i % k][1] -= 1
			mVal = max(mVal, ans[i % k][0])
	print(mVal)
	t -= 1


t = int(input())
while t:
	t -= 1
	(n, k) = map(int, input().split())
	ls = list(map(int, input().split()))
	nls = [0] * k
	for i in range(n):
		nls[i % k] += ls[i]
	nmax = max(nls)
	for i in range(n - k):
		nls[i % k] -= ls[i]
		if nls[i % k] > nmax:
			nmax = nls[i % k]
	print(nmax)


t = int(input())
while t:
	(n, k) = map(int, input().split(' '))
	ls = [int(i) for i in input().split(' ')]
	ls.reverse()
	ans = [0] * n
	for i in range(n):
		if i < k:
			ans[i] = ls[i]
		else:
			ans[i] += ans[i - k] + ls[i]
	print(max(ans))
	t -= 1


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	l = list(map(int, input().split()))
	if n == 1:
		print(*l)
		continue
	pref = []
	for i in range(len(l)):
		if i < k:
			pref.append(l[i])
		else:
			q = l[i] + pref[i - k]
			pref.append(max(q, l[i]))
	if k >= n:
		print(max(l))
	else:
		u = l[-1]
		for i in range(1, k + 1):
			if pref[-i] > u:
				u = pref[-i]
		print(u)


T = int(input())
for i in range(T):
	(n, k) = map(int, input().split())
	a = [int(i) for i in input().split()][:n]
	for i in range(n - 1, -1, -1):
		if i + k < n:
			a[i] += a[i + k]
	print(max(a))


for _ in range(int(input())):
	(a, b) = map(int, input().split(' '))
	c = list(map(int, input().split()))
	for i in range(a, -1, -1):
		if i + b < a:
			c[i] += c[i + b]
	print(max(c))


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	b = [0] * n
	for j in range(n - 1, -1, -1):
		if j + k < n:
			a[j] += a[j + k]
		else:
			a[j] = a[j]
	print(max(a))


for t in range(int(input())):
	(n, k) = list(map(int, input().split()))
	lst = list(map(int, input().split()))
	max_value = lst[-1]
	store = 0
	for i in range(len(lst) - 1, -1, -1):
		if i + k < len(lst):
			lst[i] += lst[i + k]
		max_value = max(max_value, lst[i])
	print(max_value)


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


T = int(input())
while T != 0:
	(N, K) = map(int, input().split())
	value_sqauare = list(map(int, input().split()))
	value_sqauare = value_sqauare
	for i in range(N - 1, -1, -1):
		if i + K < N:
			value_sqauare[i] = value_sqauare[i] + value_sqauare[i + K]
		else:
			value_sqauare[i] = value_sqauare[i]
	print(max(value_sqauare))
	T -= 1


for i in range(int(input())):
	(n, k) = map(int, input().split())
	arr = list(map(int, input().split()))
	ans = []
	arr.reverse()
	total = max(arr)
	for i in range(k):
		pos = 0
		for j in range(i, n, k):
			pos += arr[j]
			ans.append(pos)
	print(max(ans))


def answer():
	ans = -float('inf')
	for i in range(min(n, k)):
		val = 0
		for j in range(i, n, k):
			val = max(a[j], val + a[j])
		ans = max(ans, val)
	return ans
for T in range(int(input())):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	print(answer())


t = int(input())
for i in range(t):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	a.reverse()
	ar = []
	for i in range(k):
		c = 0
		for j in range(i, n, k):
			c += a[j]
			ar.append(c)
	print(max(ar))


t = int(input())
while t:
	t -= 1
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	ma = a[-1]
	for i in range(n - 1, n - k - 1, -1):
		if a[i] > ma:
			ma = a[i]
	for i in range(n - 1 - k, -1, -1):
		a[i] = a[i] + a[i + k]
		if a[i] > ma:
			ma = a[i]
	print(ma)


t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	input1 = list(map(int, input().split()))
	sum1 = 0
	max1 = -1000000000.0
	for i in range(k):
		for j in range(n - i - 1, -1, -k):
			sum1 = sum1 + input1[j]
			max1 = max(max1, sum1)
		sum1 = 0
	print(max1)


T = int(input())
ans = []
for _ in range(T):
	(N, K) = [int(i) for i in input().split()]
	A = [int(i) for i in input().split()]
	S = [[] for i in range(K)]
	for i in range(N):
		S[i % K].append(A[i])
	m = -float('inf')
	for i in range(K):
		s = 0
		smax = -float('inf')
		for j in range(len(S[i]) - 1, -1, -1):
			s += S[i][j]
			if s > smax:
				smax = s
		if smax > m:
			m = smax
	ans.append(m)
for i in ans:
	print(i)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	l = []
	for i in range(n):
		if i < k:
			l.append(a[i])
		else:
			l.append(max(a[i] + l[i - k], a[i]))
	m = float('-Inf')
	while l and k:
		m = max(l.pop(), m)
		k -= 1
	print(m)


test = int(input())
for _ in range(test):
	(n, k) = map(int, input().split())
	ls = list(map(int, input().split()))
	s = [0] * n
	for i in range(k):
		for j in range(n - 1 - i, -1, -k):
			if j + k >= n:
				s[j] = ls[j]
			else:
				s[j] = ls[j] + s[j + k]
	print(max(s))


import sys
t = int(input())
for tt in range(t):
	(n, k) = map(int, input().split())
	spaces = list(map(int, input().split()))
	points = [0] * n
	for i in range(k):
		for j in range(n - 1 - i, -1, -k):
			if j + k >= n:
				points[j] = spaces[j]
			else:
				points[j] = spaces[j] + points[j + k]
	print(max(points))


import numpy as np
import string
import sys
from collections import defaultdict
from bisect import bisect_left
from collections import Counter, deque
from queue import Queue
import math
for i in range(int(input())):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	arr = a[:]
	for i in range(n - 1 - k, -1, -1):
		arr[i] = arr[i + k] + a[i]
	print(max(arr))


t = int(input())
while t > 0:
	(n, k) = map(int, input().split())
	l = list(map(int, input().split()))
	x = -99999999
	for i in range(k):
		s = 0
		for j in range(n - i - 1, -1, -k):
			s += l[j]
			x = max(x, s)
	print(x)
	t -= 1


for i in range(int(input())):
	(N, K) = map(int, input().split())
	A = list(map(int, input().split()))
	score = [0] * N
	for i in range(K):
		score[N - 1 - i] = A[N - i - 1]
	for i in range(N - 1 - K, -1, -1):
		score[i] = A[i] + score[i + K]
	print(max(score))


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	l = list(map(int, input().split()))
	z = [0 for i in range(n)]
	for i in range(n - 1, -1, -1):
		if i + k > n - 1:
			z[i] = l[i]
			continue
		z[i] = z[i + k] + l[i]
	print(max(z))


for _ in range(int(input())):
	(n, step) = map(int, input().split())
	arr = [int(i) for i in input().split()]
	idds = [i for i in range(0, n - step)]
	sums = [-(int(1000000000.0) + 69)] * n
	sums += arr[n - step:]
	modfied_ids = []
	idd = 0
	for i in range(n):
		modfied_ids.append(idd)
		idd += 1
		if idd == step:
			idd = 0
	for i in range(n):
		temp = max(sums[modfied_ids[i]], sums[modfied_ids[i]] + arr[i])
		if temp < arr[i]:
			sums[modfied_ids[i]] = arr[i]
		else:
			sums[modfied_ids[i]] += arr[i]
	print(max(sums))


from math import sqrt

def solve():
	a = list(map(int, input().split()))
	n = a[0]
	k = a[1]
	x = list(map(int, input().split()))
	y = n * [-1]
	for i in range(n - k, n):
		y[i] = x[i]
	for i in range(n - k - 1, -1, -1):
		if y[i] == -1:
			y[i] = x[i] + y[i + k]
	print(max(y))
t = int(input())
for tt in range(0, t):
	solve()


def findsum(b):
	c = g = b[0]
	n = len(b)
	for i in range(1, n):
		c += b[i]
		if g < c:
			g = c
	return g
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	ans = -10 ** 15
	if k >= n:
		print(max(a))
		continue
	a.reverse()
	for i in range(k):
		ans = max(ans, findsum(a[i::k]))
	print(ans)


import numpy as np
from sys import stdin, stdout

def solve():
	for _ in range(int(input())):
		(n, k) = map(int, input().split())
		a = list(map(int, input().split()))
		ans = -10 ** 15
		if k >= n:
			print(max(a))
			continue
		a.reverse()
		for i in range(k):
			c = g = a[i]
			b = a[i:n:k]
			for j in range(1, len(b)):
				c += b[j]
				if g < c:
					g = c
			ans = max(ans, g)
		print(ans)
solve()


T = int(input())
for i in range(T):
	(N, K) = map(int, input().split())
	s = list(map(int, input().split()))
	c = [0] * N
	for i in range(N - 1, -1, -1):
		c[i] = s[i]
		if i + K < N:
			c[i] += c[i + K]
	print(max(c))


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	cost = list(map(int, input().split()))
	finalans = [-1] * n
	for i in range(n - 1, -1, -1):
		finalans[i] = cost[i]
		if i + k < n:
			finalans[i] += finalans[i + k]
	print(max(finalans))


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


for _ in range(int(input())):
	(N, K) = map(int, input().split())
	score = list(map(int, input().split()))
	array = [0] * N
	for i in range(N - 1, -1, -1):
		array[i] = score[i]
		if i + K < N:
			array[i] = array[i] + array[i + K]
	print(max(array))


t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	arr = list(map(int, input().strip().split()))[:n]
	for i in range(1, k + 1):
		for j in range(n - i - k, -1, -k):
			arr[j] = arr[j] + arr[j + k]
	print(max(arr))


t = int(input())
for _ in range(t):
	(n, k) = [int(i) for i in input().split()]
	arr = [int(i) for i in input().split()]
	dp = [0] * n
	for i in range(n - 1, -1, -1):
		dp[i] = arr[i]
		if i + k < n:
			dp[i] = dp[i] + dp[i + k]
	print(max(dp))


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	l = list(map(int, input().split()))
	l1 = []
	if m > n:
		print(max(l))
	else:
		for i in range(m):
			a = l[i]
			for j in range(i + m, n, m):
				a = max(l[j] + a, l[j])
			l1.append(a)
		print(max(l1))


t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	arr = list(map(int, input().split()))
	score = []
	jump = 0
	for i in range(1, k + 1):
		jump = -i
		sum1 = 0
		while jump >= -n:
			sum1 += arr[jump]
			score.append(sum1)
			jump -= k
	print(max(score))


t = int(input())
for i in range(t):
	(n, k) = map(int, input().split())
	squareValues = input().split()
	A = list(map(int, squareValues))
	for i in range(n - k - 1, -1, -1):
		A[i] = A[i] + A[i + k]
	print(max(A))


t = int(input())
for test in range(t):
	(n, k) = map(int, input().split())
	A = [int(x) for x in input().split()]
	for start in range(n - k - 1, -1, -1):
		A[start] += A[start + k]
	print(max(A))


for __ in range(int(input())):
	(n, k) = map(int, input().split())
	l = list(map(int, input().split()))
	dp = l[:]
	for i in range(n):
		if i - k >= 0:
			dp[i] = max(l[i], dp[i - k] + l[i])
	if k >= n:
		print(max(l))
	else:
		print(max(dp[n - k:n]))


t = int(input())
while t > 0:
	b = []
	tot = 0
	(n, k) = map(int, input().split())
	a = [int(k) for k in input().split()]
	for i in range(0, k):
		tot = sum(a[i:n:k])
		b.append(tot)
		tot = 0
	for i in range(k, n):
		b.append(b[i - k] - a[i - k])
	print(max(b))
	t -= 1


tc = int(input())
ls = []
m = 0
for i in range(tc):
	(n, k) = map(int, input().split())
	for m in range(0, n):
		ls.append(0)
	all = [int(i) for i in input().split()]
	for j in range(len(all) - 1, -1, -1):
		if j + k < n:
			ls[j] = all[j] + ls[j + k]
		else:
			ls[j] = all[j]
	print(max(ls))
	ls.clear()


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	a = [int(i) for i in input().split()]
	bs = [-9999999] * k
	cs = [0] * k
	for i in range(len(a) - 1, -1, -1):
		j = i % k
		cs[j] += a[i]
		if bs[j] < cs[j]:
			bs[j] = cs[j]
	print(max(bs))


def summ(b):
	s = 0
	for i in b:
		if s < 0:
			s = 0
		s += i
	return s
t = int(input())
for i in range(t):
	(n, k) = map(int, input().split(' '))
	step = list(map(int, input().split(' ')))
	a = []
	for j in range(k):
		b = step[j::k]
		s1 = summ(b)
		a.append(s1)
	print(max(a))


def getMax(arr):
	s = -999999999
	sm = 0
	for i in range(len(arr)):
		if sm < 0:
			sm = 0
		sm += arr[i]
	return sm
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	if k >= n:
		print(max(a))
	else:
		s = -9999999
		for i in range(k):
			sm = getMax(a[i::k])
			s = max(s, sm)
		print(s)


def getMax(arr):
	s = -9999999999999999999
	sm = 0
	for i in range(len(arr)):
		sm += arr[i]
		s = max(s, sm)
	return s
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	maxi = 0
	a = a[::-1]
	if k >= n:
		print(max(a))
	else:
		s = -9999999999999
		for i in range(k):
			sm = getMax(a[i::k])
			s = max(s, sm)
		print(s)


t = int(input())
for i in range(t):
	(a, k) = map(int, input().split())
	l = list(map(int, input().split()))
	final = [0] * k
	for j in range(len(l)):
		a = j % k
		if final[a] + l[j] > l[j]:
			final[a] = final[a] + l[j]
		else:
			final[a] = l[j]
	print(max(final))


MIN = -100000

def maximum(a):
	s = MIN
	sa = 0
	for ai in a:
		sa += ai
		s = max(s, sa)
	return s
for T in range(int(input())):
	(N, K) = map(int, input().split())
	A = list(reversed(list(map(int, input().split()))))
	score = MIN
	if K >= N:
		score = max(A)
	else:
		for i in range(K):
			score = max(score, maximum(A[i::K]))
	print(score)


MIN = -1000000

def maximum(a):
	s = MIN
	sa = 0
	for ai in a:
		sa += ai
		s = max(s, sa)
	return s
for T in range(int(input())):
	(N, K) = map(int, input().split())
	A = list(map(int, input().split()))
	score = MIN
	if N > 1000:
		jumps = list()
		for i in range(K + 1):
			jumps.append(list(reversed(A[i::K])))
		for jump in jumps:
			score = max(score, maximum(jump))
		score = max(max(A), score)
	else:
		for i in range(N):
			score = max(score, sum(A[i::K]))
	print(score)


for test in range(int(input())):
	(n, k) = map(int, input().split())
	arr = list(map(int, input().split()))
	if k > n:
		print(max(arr))
		continue
	for i in range(n - k - 1, -1, -1):
		arr[i] = arr[i] + arr[i + k]
	print(max(arr))


t = int(input())
for i in range(t):
	(n, k) = map(int, input().split())
	A = list(map(int, input().split()))
	dp = []
	ans = A[n - 1]
	for i in range(n - 1, -1, -1):
		if i + k < n:
			A[i] += A[i + k]
		ans = max(ans, A[i])
	print(ans)


t = int(input())
for z in range(0, t):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	b = []
	for i in range(0, k):
		b.append(sum(a[i:n:k]))
	for i in range(k, n):
		b.append(b[i - k] - a[i - k])
	print(max(b))


import sys
t = int(input())
for i in range(t):
	list1 = list(map(int, input().split()))
	n = int(list1[0])
	k = int(list1[1])
	s = list(map(int, input().split()))
	s1 = [-sys.maxsize - 1 for i in range(n)]
	for j in range(n):
		loc = j % k
		if s[j] + s1[loc] < s[j]:
			s1[loc] = s[j]
		else:
			s1[loc] += s[j]
	s5 = s1[0:k + 1]
	max1 = max(s5)
	print(max1)


T = int(input())
for i in range(T):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	pref = [0] * n
	maxi = -10001
	for j in range(k):
		pref[n - j - 1] = a[n - j - 1]
	for j in range(n - k - 1, -1, -1):
		pref[j] = pref[j + k] + a[j]
	for j in range(n):
		if maxi < pref[j]:
			maxi = pref[j]
	print(maxi)


T = int(input())
while T:
	(N, K) = input().split()
	N = int(N)
	K = int(K)
	A = input().split()
	for i in range(N):
		A[i] = int(A[i])
	if K > N:
		print(max(A))
	else:
		sum1 = [0 for i in range(K)]
		sum2 = []
		for i in range(N):
			sum1[(N - 1 - i) % K] += A[N - 1 - i]
			sum2.append(sum1[(N - 1 - i) % K])
		print(max(sum2))
	T -= 1


t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	a = []
	ans = []
	a = list(map(int, input().split()))
	for i in range(k):
		jump = i
		sum = 0
		while jump < n:
			sum += a[jump]
			jump += k
		ans.append(sum)
		if i == 0:
			max = sum
		elif sum > max:
			max = sum
	for i in range(k, n):
		ans.append(ans[i - k] - a[i - k])
		if ans[i] > max:
			max = ans[i]
	print(max)


t = int(input())
while t != 0:
	list_a = [int(x) for x in input().split()]
	(n, k) = list_a
	list_b = [int(x) for x in input().split()]
	if n == k:
		cur_max = max(list_b)
	else:
		dist_first_k_ele = []
		for i in range(k):
			dist_first_k_ele.append(sum(list_b[i:len(list_b):k]))
		cur_max = max(dist_first_k_ele)
		for i in range(k, len(list_b)):
			dist_first_k_ele[i % k] = dist_first_k_ele[i % k] - list_b[i - k]
			if cur_max < dist_first_k_ele[i % k]:
				cur_max = dist_first_k_ele[i % k]
	t -= 1
	print(cur_max)


import math
for testcases in range(int(input())):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	a.reverse()
	maxi = a[0]
	temp = a[0]
	flag = 1
	j = k
	while j < n:
		temp = temp + a[j]
		j = j + k
		maxi = max(maxi, temp)
	temp = 0
	for i in range(1, k):
		j = i
		while j < n:
			temp = temp + a[j]
			j += k
			maxi = max(maxi, temp)
		temp = 0
	print(maxi)


t = int(input())
for i in range(t):
	(n, k) = map(int, input().split())
	arr = [int(x) for x in input().split()]
	for j in range(n - 1, -1, -1):
		if j + k < n:
			arr[j] += arr[j + k]
	print(max(arr))


tests = int(input())
for te in range(tests):
	(n, k) = list(map(int, input().split()))
	arr = list(map(int, input().split()))
	count = 0
	for i in range(n):
		if arr[i] < 0:
			count += 1
	ans = -10 ** 18
	for i in range(k):
		j = i
		suma = 0
		while j < n:
			suma += arr[j]
			if suma < 0 and j + k < n:
				suma = 0
			j = j + k
		ans = max(ans, suma)
	print(ans)