You are given an array $a$ with $n$ integers. You can perform the following operation at most $k$ times:

Choose two indices $i$ and $j$, in which $i \,mod\, k = j \,mod\, k$ ($1 \le i < j \le n$).

Swap $a_i$ and $a_j$.

After performing all operations, you have to select $k$ consecutive elements, and the sum of the $k$ elements becomes your score. Find the maximum score you can get.

Here $x mod y$ denotes the remainder from dividing $x$ by $y$.


-----Input-----

The first line contains one integer $t$ ($1 \le t \le 600$) — the number of test cases.

Each test case consists of two lines.

The first line of each test case contains two integers $n$ and $k$ ($1 \le k \le n \le 100$) — the length of the array and the number in the statement above.

The second line of each test case contains $n$ integers $a_1, a_2, \ldots, a_n$ ($0 \le a_i \le 10^9$)  — the array itself.


-----Output-----

For each test case, print the maximum score you can get, one per line.


-----Examples-----

Input
5
3 2
5 6 0
1 1
7
5 3
7 0 4 0 4
4 2
2 7 3 4
3 3
1000000000 1000000000 999999997
Output
11
7
15
10
2999999997


-----Note-----

In the first test case, we can get a score of $11$ if we select $a_1, a_2$ without performing any operations.

In the third test case, we can get a score of $15$ if we first swap $a_1$ with $a_4$ and then select $a_3, a_4, a_5$.

Difficulty: EASY
Tags: Sorting

Greedy algorithms
Skill types: Sorting

Greedy algorithms

Starter code:

Solutions:
def read():
	(n, k) = map(int, input().split())
	in_list = list(map(int, input().split()))
	return (n, k, in_list)

def solve():
	ans = [0] * k
	for (idx, value) in enumerate(in_list):
		rem = (idx + 1) % k
		if value > ans[rem]:
			ans[rem] = value
	return sum(ans)
case = int(input())
for it in range(case):
	(n, k, in_list) = read()
	ans = solve()
	print(ans)
pass


def myMax(a, k):
	spec = [0] * k
	for i in range(len(a)):
		if spec[i % k] < a[i]:
			spec[i % k] = a[i]
	return spec
t = int(input())
for i in range(t):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	a = myMax(a, k)
	print(sum(a))


def solution():
	numCases = int(input())
	data = []
	for i in range(numCases * 2):
		data.append(input())
	for case in range(0, len(data), 2):
		n = int(data[case].split(' ')[0])
		k = int(data[case].split(' ')[1])
		a = [int(x) for x in data[case + 1].split(' ')]
		if n == k:
			print(sum(a))
			continue
		seperated = [[] for x in range(k)]
		for i in range(n):
			seperated[i % k].append(a[i])
		for ka in seperated:
			ka.sort()
		print(sum([b[-1] for b in seperated]))
	return
solution()


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	if n == k:
		print(sum(a))
	else:
		p = []
		for i in range(k):
			maxx = max(0, a[i])
			j = i + k
			while j < n:
				maxx = max(maxx, a[j])
				j += k
			p.append(maxx)
		print(sum(p))


times = int(input())
for time in range(times):
	(n, k) = [int(x) for x in input().split()]
	arr = [int(x) for x in input().split()]
	for i in range(n):
		for j in range(i + k, n, k):
			if arr[i] < arr[j]:
				(arr[i], arr[j]) = (arr[j], arr[i])
	s = 0
	for i in range(k):
		s += arr[i]
	print(s)


N = int(input())
dd = []
for i in range(N):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	aa = [0] * (k + 1)
	d = 0
	for i in range(n):
		if a[i] > aa[d]:
			aa[d] = a[i]
		d = d + 1
		if d == k:
			d = 0
	f = 0
	for t in aa:
		f = f + t
	dd.append(f)
for t in dd:
	print(t)


t = int(input())
ans = []
for i in range(t):
	(n, k) = map(int, input().split())
	lst = list(map(int, input().split()))
	lst = [[lst[i - 1], i % k] for i in range(1, n + 1)]
	lst.sort(key=lambda x: x[0], reverse=True)
	sum = 0
	lst1 = [i for i in range(k + 1)]
	for i in lst:
		if len(lst1) == 0:
			break
		if i[1] in lst1:
			sum += i[0]
			lst1.remove(i[1])
	ans.append(sum)
for i in ans:
	print(i)


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


for i in range(int(input())):
	(n, k) = map(int, input().split())
	arr = list(map(int, input().split()))
	if len(arr) <= k:
		print(sum(arr))
	else:
		a = [0] * k
		for i in range(n):
			m = i // k
			a[i % k] = max(a[i % k], arr[i])
		print(sum(a))


import sys
input = lambda : sys.stdin.readline().rstrip()
in_il = lambda : list(map(int, input().split()))
in_sl = lambda : input().split()
in_i = lambda : int(input())
MAX_INT = float('inf')

def solve():
	(n, k) = in_il()
	arr = in_il()
	for i in range(k):
		for j in range(i + k, n, k):
			arr[i] = max(arr[i], arr[j])
	print(sum(arr[:k]))
for _ in range(in_i()):
	solve()


n = int(input())
for i in range(n):
	(n, m) = map(int, input().split())
	res = [0] * m
	arr = list(map(int, input().split()))
	for i in range(n):
		res[(i + 1) % m] = max(res[(i + 1) % m], arr[i])
	print(sum(res))


t = int(input())
for i in range(t):
	(n, k) = list(map(int, input().split()))
	a = list(map(int, input().split()))
	if n == k:
		print(sum(a))
	else:
		tmax = [-1 for x in range(k)]
		for j in range(k):
			tmp = j
			while tmp < n:
				if tmax[j] < a[tmp]:
					tmax[j] = a[tmp]
				tmp += k
		print(sum(tmax))


for i in range(int(input())):
	(n, pas) = map(int, input().split())
	t = [int(x) for x in input().split()]
	print(sum([max(t[j::pas]) for j in range(pas)]))


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


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	arr = list(map(int, input().split()))
	for i in range(k, n):
		arr[i % k] = max(arr[i % k], arr[i])
	print(sum(arr[:k]))


t = int(input())

def solve():
	(n, k) = map(int, input().split())
	arr = list(map(int, input().split()))
	mod = [[] for i in range(k)]
	for i in range(n):
		mod[(i + 1) % k].append(arr[i])
	sum = 0
	for item in mod:
		sum += max(item)
	print(sum)
for i in range(t):
	solve()


def func():
	(n, k) = map(int, input().split())
	arr = input().split()
	arr = [int(i) for i in arr]
	mods = [0] * k
	for i in range(n):
		if mods[i % k] < arr[i]:
			mods[i % k] = arr[i]
	print(sum(mods))
n_tests = int(input())
for i in range(n_tests):
	func()


class Solution:

	def maxScore(self, arr, k):
		if len(arr) == k:
			return sum(arr)
		arr = [0] + arr
		res = 0
		for j in range(1, k + 1):
			currMax = -float('inf')
			for i in range(j, len(arr), k):
				currMax = max(currMax, arr[i])
			res += currMax
		return res
ob = Solution()
for _ in range(int(input())):
	(n, k) = list(map(int, input().strip().split()))
	arr = list(map(int, input().strip().split()))
	print(ob.maxScore(arr, k))


import sys

def inp():
	return int(input())

def inlt():
	return list(map(int, input().split()))

def insr():
	s = input()
	return list(s[:len(s) - 1])

def invr():
	return map(int, input().split())

def main():
	t = inp()
	for i in range(t):
		(n, k) = inlt()
		A = inlt()
		M = [0 for i in range(k)]
		for (i, a) in enumerate(A):
			if a > M[i % k]:
				M[i % k] = a
		print(sum(M))
main()


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


t = int(input())
for _ in range(t):
	(n, k) = [int(x) for x in input().split()]
	l = [int(x) for x in input().split()]
	if k == n:
		print(sum(l))
	else:
		it = n // k
		s = 0
		maxi = 0
		for i in range(k):
			maxi = 0
			for j in range(it):
				maxi = max(maxi, l[j * k + i])
			if it * k + i < n:
				maxi = max(maxi, l[it * k + i])
			s = s + maxi
		print(s)


import sys
import math
from collections import Counter

def gi():
	return list(map(int, sys.stdin.readline().strip().split()))

def gs():
	return sys.stdin.readline().strip()

def fun(a, k):
	i = 0
	res = 0
	l = len(a)
	z = k
	while k:
		val = -1
		ptr = i
		while ptr < l:
			val = max(val, a[ptr])
			ptr += z
		res += val
		k -= 1
		i += 1
	return res
for _ in range(int(input())):
	z = gi()
	a = gi()
	print(fun(a, z[-1]))


for p in range(int(input())):
	(n, k) = map(int, input().split())
	a = [int(v) for v in input().split()]
	print(sum((max(a[i::k]) for i in range(k))))


t = int(input())
for _ in range(t):
	(n, k) = [int(x) for x in input().split(' ')]
	seq = [int(x) for x in input().split(' ')]
	mem = {}
	if k == len(seq):
		print(sum(seq))
		continue
	for x in range(k):
		mem[x] = 0
	for (i, item) in enumerate(seq):
		idx = i % k
		if item > mem[idx]:
			mem[idx] = item
	ans = 0
	for val in mem.values():
		ans += val
	print(ans)


R = lambda : map(int, input().split())
(t,) = R()
for k in range(t):
	(n, k) = R()
	l = list(R())
	maxmod = [0] * k
	for i in range(n):
		if l[i] > maxmod[i % k]:
			maxmod[i % k] = l[i]
	print(sum(maxmod))


x = int(input())
for q in range(x):
	(k, b) = map(int, input().split())
	a = list(map(int, input().split()))
	ans = [0] * b
	for i in range(0, k):
		ans[(i + 1) % b] = max(ans[(i + 1) % b], a[i])
	print(sum(ans))


def divided(a, k):
	summ = 0
	b = list(list())
	for j in range(k):
		b.append(a[j::k])
	for j in range(k):
		summ += max(b[j])
	return summ
t = int(input())
for tc in range(t):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	sum = 0
	print(divided(a, k))


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	s = [0] * k
	for i in range(n):
		if a[i] > s[i % k]:
			s[i % k] = a[i]
	print(sum(s))


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


import sys
t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	a_min = min(a)
	sum_l = [a_min] * k
	for i in range(n):
		if sum_l[i % k] < a[i]:
			sum_l[i % k] = a[i]
	print(sum(sum_l))


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	arr = list(map(int, input().split()))
	arr_out = [0 for x in range(n + 2)]
	for x in range(n):
		m = (x + 1) % k
		if arr_out[m] < arr[x]:
			arr_out[m] = arr[x]
	print(sum(arr_out))


def solve():
	[n, k] = [int(x) for x in input().split()]
	a = [int(x) for x in input().split()]
	s = 0
	for i in range(0, k):
		count = i
		maxR = 0
		while count < n:
			maxR = max(maxR, a[count])
			count += k
		s += maxR
	print(s)
for _ in range(int(input())):
	solve()


test = int(input())
for _ in range(test):
	(num, kl) = list(map(int, input().split()))
	a = list(map(int, input().split()))
	su = 0
	for i in range(kl):
		su += max(a[i::kl])
	print(su)


for case in range(int(input())):
	(n, k) = list(map(lambda x: int(x), input().split(' ')))
	num_arr = list(map(lambda x: int(x), input().split(' ')))
	if k == n:
		print(sum(num_arr))
	else:
		score = 0
		for swap_count in range(k):
			indexed_arr = []
			for i in range(swap_count, n, k):
				indexed_arr.append(num_arr[i])
			score += max(indexed_arr)
		print(score)


t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	b = [0] * k
	x = 0
	for i in a:
		b[x] = max(b[x], i)
		x = (x + 1) % k
	print(sum(b))


t = int(input())
for _ in range(t):
	nk = [int(i) for i in input().split()]
	a = [int(i) for i in input().split()]
	(n, k) = (nk[0], nk[1])
	kk = [0] * k
	for i in range(1, n + 1):
		j = i % k - 1
		if kk[j] < a[i - 1]:
			kk[j] = a[i - 1]
	print(sum(kk))


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	for i in range(len(a)):
		if a[i % k] < a[i]:
			a[i % k] = a[i]
	print(sum(a[:k]))


t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	arr = list(map(int, input().split()))
	maximums = [0] * k
	for i in range(n):
		if arr[i] > maximums[i % k]:
			maximums[i % k] = arr[i]
	print(sum(maximums))


import itertools
from math import floor, log, log2, ceil, sqrt
from itertools import groupby
from decimal import Decimal, getcontext
import sys
from collections import deque
primes = set()
maxN = 1000001

def generatePrimes():
	used = [False] * maxN
	for i in range(2, maxN):
		if not used[i]:
			primes.add(i)
			for j in range(i, maxN, i):
				used[j] = True

def isPrime(n):
	if n < 2:
		return True
	x = 2
	while x * x <= n:
		if n % x == 0:
			return False
		x += 1
	return True

def gcd(x, y):
	while y != 0:
		(x, y) = (y, x % y)
	return x
t = int(input())
for _ in range(t):
	[n, k] = list(map(int, input().split()))
	a = list(map(int, input().split()))
	d = dict()
	for i in range(n):
		if i % k in d:
			d[i % k] = max(d[i % k], a[i])
		else:
			d[i % k] = a[i]
	res = 0
	for v in d.values():
		res += v
	print(res)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	num = list(map(int, input().split()))
	s = 0
	for i in range(0, k):
		s = s + max(num[i::k])
	print(s)


def solution(ar, n, k):
	maxs = ar[:k]
	for i in range(n):
		maxs[i % k] = max(ar[i], maxs[i % k])
	return sum(maxs)
t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	ar = list(map(int, input().split()))
	print(solution(ar, n, k))


t = int(input())
while t:
	t -= 1
	(n, k) = map(int, input().split())
	lst = list(map(int, input().split()))
	dct = {x: 0 for x in range(0, k)}
	for i in range(n):
		if dct[i % k] < lst[i]:
			dct[i % k] = lst[i]
	res = 0
	for i in dct.values():
		res += i
	print(res)


T = int(input())
for t in range(0, T):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	if k == n:
		print(sum(a))
	else:
		lst = [[] for i in range(0, k)]
		for i in range(0, n):
			lst[i % k].append(a[i])
		s = 0
		for item in lst:
			s += max(item)
		print(s)


for i in range(int(input())):
	(n, k) = map(int, input().split())
	l = list(map(int, input().split()))
	if len(l) <= k:
		print(sum(l))
	else:
		for i in range(k):
			j = i
			id = i
			mx = l[i]
			while j < len(l):
				if l[j] > mx:
					mx = l[j]
					id = j
				j += k
			(l[i], l[id]) = (l[id], l[i])
		ans = 0
		for i in range(k):
			ans += l[i]
		print(ans)


for _ in range(int(input())):
	(N, K) = map(int, input().split())
	A = list(map(int, input().split()))
	m = [[] for i in range(K)]
	for i in range(N):
		m[i % K].append(A[i])
	su = sum([max(x) for x in m])
	print(su)


t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	val = list(map(int, input().split()))
	i = 0
	j = i + k - 1
	while j < n - 1:
		if val[i] > val[j + 1]:
			(val[i], val[j + 1]) = (val[j + 1], val[i])
		i += 1
		j += 1
	print(sum(val[::-1][:k]))


import sys
input = sys.stdin.readline

def inp():
	return int(input())

def inlt():
	return list(map(int, input().split()))

def insr():
	s = input()
	return list(s[:len(s) - 1])

def invr():
	return map(int, input().split())

def mainak(n):
	ts = 0
	for (idx, i) in enumerate(n):
		if i > n[ts]:
			ts = idx
	return ts + 1
t = inp()
for _ in range(t):
	(n, k) = [int(x) for x in input().strip().split()]
	nu = [int(x) for x in input().strip().split()]
	nu = [1] + nu
	i = 1
	ans = 0
	while i <= k:
		j = i
		m = 0
		while j < len(nu):
			if nu[j] > m:
				m = nu[j]
			j += k
		ans += m
		i += 1
	print(ans)


def solution(n, k, arr):
	for i in range(k):
		j = i + k
		while j < n:
			if arr[j] > arr[i]:
				tmp = arr[i]
				arr[i] = arr[j]
				arr[j] = tmp
			j += k
	return sum(arr[:k])
t = int(input())
while t:
	(n, k) = [int(x) for x in input().strip().split(' ')]
	arr = [int(x) for x in input().strip().split(' ')]
	print(solution(n, k, arr))
	t -= 1


import sys
input = lambda : sys.stdin.readline().rstrip()
ii = lambda : int(input())
mi = lambda : map(int, input().split())
li = lambda : list(mi())
inf = 2 ** 63 - 1
mod = 998244353

def solve():
	(x, y) = mi()
	l = li()
	out = [0] * x
	for i in range(x):
		out[(i + 1) % y] = max(out[(i + 1) % y], l[i])
	result = 0
	for i in range(y):
		result += out[i]
	print(result)
for _ in range(ii()):
	solve()


n = int(input())
for i in range(n):
	m = list(map(int, input().split()))
	k = m[1]
	d = {}
	arr = list(map(int, input().split()))
	for j in range(len(arr)):
		if (j + 1) % k not in d:
			d[(j + 1) % k] = arr[j]
		else:
			d[(j + 1) % k] = max(d[(j + 1) % k], arr[j])
	ans = 0
	for j in d:
		ans += d[j]
	print(ans)


import sys
t = int(sys.stdin.readline())
for _ in range(t):
	(n, k) = map(int, sys.stdin.readline().split())
	a = list(map(int, sys.stdin.readline().split()))
	b = [0] * (n + 1)
	for i in range(n):
		b[i % k] = max(b[i % k], a[i])
	s = sum(b[:k])
	print(s)


t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	arr = list(map(int, input().split()))
	mx = sum([max([x for x in arr[i::k]]) for i in range(k)])
	print(mx)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	arr = list(map(int, input().split()))
	if n == k:
		print(sum(arr))
	else:
		ml = []
		for i in range(k):
			m = arr[i]
			for j in range(i + k, n, k):
				m = max(arr[j], m)
			ml.append(m)
		print(sum(ml))


for _ in range(int(input())):
	[n, k] = list(map(int, input().split()))
	a = list(map(int, input().split()))
	d = []
	s = 0
	for i in range(k):
		m = a[i]
		for j in range(i, n, k):
			if a[j] > m:
				m = a[j]
		s += m
	print(s)


for _ in range(int(input())):
	(n, k) = map(int, input().split(' '))
	arr = list(map(int, input().split(' ')))
	lst = []
	for i in range(k):
		lst.append([])
	for i in range(n):
		lst[i % k].append(arr[i])
	sum = 0
	for i in lst:
		sum = sum + max(i)
	print(sum)


for i in range(int(input())):
	(n, k) = map(int, input().split())
	arr = list(map(int, input().split()))
	sum = 0
	l = 0
	for j in range(n):
		if j + k >= n:
			break
		elif arr[j] > arr[j + k]:
			arr[j + k] = arr[j]
	while l < k:
		sum += arr[n - 1 - l]
		l += 1
	print(sum)


import sys
m = int(sys.stdin.readline())

def f(a, n, k):
	u = [-1000] * k
	for i in range(k):
		p = 0
		while p + i < n:
			u[i] = max(u[i], int(a[p + i]))
			p += k
	return sum(u)
for i in range(m):
	w = sys.stdin.readline().replace('\n', '').split(' ')
	a = sys.stdin.readline().replace('\n', '').split(' ')
	print(f(a, int(w[0]), int(w[1])))


for i in range(int(input())):
	(n, k) = map(int, input().split())
	l = list(map(int, input().split()))
	c = 0
	if n == k:
		print(sum(l))
		c = 1
	for j in range(1, n + 1):
		t = j + k
		while t <= n:
			if l[j - 1] < l[t - 1]:
				l[j - 1] = l[t - 1]
			t += k
	if c == 0:
		print(sum(l[:k]))


for l in range(int(input())):
	(n, k) = [int(i) for i in input().split()]
	s = 0
	a = [int(i) for i in input().split()]
	b = [0 for i in range(len(a))]
	for i in range(len(a)):
		b[i % k] = max(a[i], b[i % k])
	for i in range(k):
		s = s + b[i]
	print(s)


def consecutiveSum(a, b, array):
	if b >= a:
		print(sum(array))
	else:
		my_sum = 0
		index = 0
		while index < b:
			my_sum += max(array[index::b])
			index += 1
		print(my_sum)

def ruleOfLeague(n, x, y):
	if x == 0 and y == 0:
		print(-1)
	elif x == 0 or y == 0:
		number = 0
		if x != 0:
			number = x
		else:
			number = y
		if n == 1:
			print(1)
		elif n == 2:
			print(2)
		elif (n - 1) % number != 0:
			print(-1)
		else:
			player = list(range(1, n + 1))
			player = player[1::number]
			winner = [1] + player[1:]
			for_print = []
			for each in winner:
				for_print += [each] * number
			print(' '.join(list(map(str, for_print))))
	else:
		print(-1)
a = int(input())
while a > 0:
	b = input().split()
	c = list(map(int, input().split()))
	consecutiveSum(int(b[0]), int(b[1]), c)
	a -= 1


t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	res = [0] * k
	arr = list(map(int, input().split()))
	for i in range(n):
		res[(i + 1) % k] = max(res[(i + 1) % k], arr[i])
	print(sum(res))


def solve(l, n, k):
	res = 0
	for i in range(k):
		cur = []
		j = i
		while j >= 0:
			cur += [l[j]]
			j += k
			if j >= n:
				break
		res += max(cur)
	print(res)
	return
t = int(input())
for x in range(t):
	(n, k) = [int(i) for i in input().split()]
	l = [int(i) for i in input().split()]
	solve(l, n, k)


import sys
input = sys.stdin.readline
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	x = tuple(map(int, input().split()))
	maxelements = [0] * k
	for i in range(n):
		maxelements[i % k] = max(maxelements[i % k], x[i])
	print(sum(maxelements))


NumberofTestCases = int(input())

def ConsecutiveSum(arr, N, K):
	temp = [0 for _ in range(K)]
	for (i, el) in enumerate(arr):
		temp[i % K] = max(temp[i % K], el)
	print(sum(temp))
for i in range(NumberofTestCases):
	(N, K) = map(int, input().split())
	arr = list(map(int, input().split()))
	ConsecutiveSum(arr, N, K)


test = int(input())
while test != 0:
	(n, k) = [int(x) for x in input().split()]
	a = [int(x) for x in input().split()]
	total = 0
	if n == k:
		print(sum(a))
	else:
		for i in range(k):
			maxm = a[i]
			t = k
			while i + t < n:
				maxm = max(maxm, a[i + t])
				t += k
			total += maxm
		print(total)
	test -= 1


for t in range(int(input())):
	(n, k) = map(int, input().split())
	lst = [int(i) for i in input().split()]
	d = {}
	for i in range(n):
		if i % k not in d:
			d[i % k] = lst[i]
		else:
			d[i % k] = max(d[i % k], lst[i])
	res = 0
	for i in d.keys():
		res += d[i]
	print(res)


from math import *
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	mass = list(map(int, input().split()))
	p = [0] * k
	for i in range(n):
		p[(i + 1) % k] = max(p[(i + 1) % k], mass[i])
	print(sum(p))


t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	b = []
	if k > n:
		k = n
	for i in range(k):
		cmax = a[i]
		j = i + k
		while j < n:
			if cmax < a[j]:
				cmax = a[j]
			j += k
		b.append(cmax)
	print(sum(b))


def solve(arr, k):
	summ = 0
	for i in range(k):
		ind = i
		maxx = -1
		while ind < len(arr):
			maxx = max(maxx, arr[ind])
			ind += k
		summ += maxx
	return summ
for _ in range(int(input())):
	arr1 = list(map(int, input().split()))
	arr2 = list(map(int, input().split()))
	print(solve(arr2, arr1[1]))


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	l = list(map(int, input().split()))
	z = 0
	for i in range(k):
		m = 0
		while i < n:
			m = max(m, l[i])
			i += k
		z += m
	print(z)


for testcases in range(int(input())):
	S = list(map(int, input().split(' ')))
	a = list(map(int, input().split(' ')))
	n = S[0]
	k = S[1]
	print(sum((max(a[i::k]) for i in range(k))))


from collections import defaultdict
from sys import stdin as f
N = int(f.readline())
ans = []
for _ in range(N):
	(n, k) = map(int, f.readline().split())
	a = list(map(int, f.readline().split()))
	mp = defaultdict(int)
	for (i, n) in enumerate(a):
		mp[i % k] = max(mp[i % k], n)
	ans.append(sum(mp.values()))
print('\n'.join((str(x) for x in ans)))


ntestcases = int(input())
for i in range(ntestcases):
	(n, k) = map(int, input().split(' '))
	nums = list(map(int, input().split(' ')))
	for j in range(k):
		for l in range(j + k, n, k):
			nums[j] = max(nums[j], nums[l])
	print(sum(nums[0:k]))


t = int(input())
for i in range(t):
	(n, k) = map(int, input().split(' '))
	k_maxs = [0] * k
	for (j, a) in enumerate(map(int, input().split(' '))):
		k_maxs[j % k] = max(k_maxs[j % k], a)
	print(sum(k_maxs))


ta = int(input())
for i in range(ta):
	(na, ka) = map(int, input().split())
	la = list(map(int, input().split()))
	arr = la
	for j in range(len(la)):
		arr[j % ka] = max(arr[j % ka], arr[j])
	summ = 0
	for j in range(ka):
		summ += arr[j]
	print(summ)


t = int(input())
for ttt in range(t):
	(n, k) = [int(i) for i in input().split()]
	a = [int(i) for i in input().split()]
	kk = [0] * k
	for i in range(n):
		kk[i % k] = max(kk[i % k], a[i])
	print(sum(kk))


n = int(input())
for j in range(n):
	inputs = list(map(int, input().split()))
	a = list(map(int, input().split()))
	k = inputs[1]
	(l, r) = (0, k)
	while r < len(a):
		if a[l] > a[r]:
			(a[r], a[l]) = (a[l], a[r])
		l += 1
		r += 1
	print(sum(a[-k:]))


t = int(input())
while t != 0:
	t -= 1
	(n, k) = map(int, input().split())
	array = list(map(int, input().split()))
	sum = 0
	for i in range(k):
		sum += max(array[i::k])
	print(sum)


import sys
t = int(input())
for i in range(t):
	(n, k) = map(int, input().split(' '))
	arr = [int(x) for x in input().split(' ')]
	sum = 0
	for j in range(k):
		mVal = arr[j]
		idx = j + k
		while idx < n:
			mVal = max(mVal, arr[idx])
			idx += k
		sum += mVal
	print(sum)