A median of an array of integers of length $n$ is the number standing on the $\lceil {\frac{n}{2}} \rceil$ (rounding up) position in the non-decreasing ordering of its elements. Positions are numbered starting with $1$. For example, a median of the array $[2, 6, 4, 1, 3, 5]$ is equal to $3$. There exist some other definitions of the median, but in this problem, we will use the described one.

Given two integers $n$ and $k$ and non-decreasing array of $nk$ integers. Divide all numbers into $k$ arrays of size $n$, such that each number belongs to exactly one array.

You want the sum of medians of all $k$ arrays to be the maximum possible. Find this maximum possible sum.


-----Input-----

The first line contains a single integer $t$ ($1 \leq t \leq 100$) — the number of test cases. The next $2t$ lines contain descriptions of test cases.

The first line of the description of each test case contains two integers $n$, $k$ ($1 \leq n, k \leq 1000$).

The second line of the description of each test case contains $nk$ integers $a_1, a_2, \ldots, a_{nk}$ ($0 \leq a_i \leq 10^9$) — given array. It is guaranteed that the array is non-decreasing: $a_1 \leq a_2 \leq \ldots \leq a_{nk}$.

It is guaranteed that the sum of $nk$ for all test cases does not exceed $2 \cdot 10^5$.


-----Output-----

For each test case print a single integer — the maximum possible sum of medians of all $k$ arrays.


-----Examples-----

Input
6
2 4
0 24 34 58 62 64 69 78
2 2
27 61 81 91
4 3
2 4 16 18 21 27 36 53 82 91 92 95
3 4
3 11 12 22 33 35 38 67 69 71 94 99
2 1
11 41
3 3
1 1 1 1 1 1 1 1 1
Output
165
108
145
234
11
3


-----Note-----

The examples of possible divisions into arrays for all test cases of the first test:

Test case $1$: $[0, 24], [34, 58], [62, 64], [69, 78]$. The medians are $0, 34, 62, 69$. Their sum is $165$.

Test case $2$: $[27, 61], [81, 91]$. The medians are $27, 81$. Their sum is $108$.

Test case $3$: $[2, 91, 92, 95], [4, 36, 53, 82], [16, 18, 21, 27]$. The medians are $91, 36, 18$. Their sum is $145$.

Test case $4$: $[3, 33, 35], [11, 94, 99], [12, 38, 67], [22, 69, 71]$. The medians are $33, 94, 38, 69$. Their sum is $234$.

Test case $5$: $[11, 41]$. The median is $11$. The sum of the only median is $11$.

Test case $6$: $[1, 1, 1], [1, 1, 1], [1, 1, 1]$. The medians are $1, 1, 1$. Their sum is $3$.

Source: codeforces | Difficulty: EASY
Tags: Mathematics

Greedy algorithms


Solutions:
from math import ceil

def calc(n, k, a):
	a.sort()
	curr = 0
	if n == 1:
		return sum(a)
	if n == 2:
		for i in range(0, len(a), 2):
			curr += a[i]
	else:
		j = len(a) - 1 - n // 2
		c = 0
		while c < k:
			curr += a[j]
			j -= n // 2 + 1
			c += 1
	return curr
t = int(input())
for i in range(t):
	(n, k) = list(map(int, input().split()))
	a = list(map(int, input().split()))
	print(calc(n, k, a))


import math
t = int(input())
while t:
	(n, k) = input().split()
	n = int(n)
	k = int(k)
	data = [int(x) for x in input().split()]
	sum = 0
	if n == 1:
		for ele in data:
			sum += ele
		print(sum)
	elif n == 2:
		i = 0
		while i < k * n:
			sum += data[i]
			i += 2
		print(sum)
	else:
		i = n * k - (n // 2 + 1)
		while i >= k * (n - (n // 2 + 1)):
			sum += data[i]
			i = i - (n // 2 + 1)
		print(sum)
	t -= 1


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	li = list(map(int, input().split()))
	ans = li[(n - 1) // 2 * k]
	i = 1
	x = (n - 1) // 2 * k
	while i < k:
		x = x + (n // 2 + 1)
		ans = ans + li[x]
		i = i + 1
	print(ans)


t = int(input())
for q in range(t):
	(n, k) = input().split()
	n = int(n)
	k = int(k)
	a = input().split()
	s = 0
	h = n // 2 + 1
	for i in range(1, k + 1):
		s += int(a[-(i * h)])
	print(s)


from math import ceil
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	p = [*map(int, input().split())]
	ans = 0
	m = n * k - ceil(n // 2) - 1
	added = 0
	for i in range(m, -1, -ceil(n // 2) - 1):
		if added == k:
			break
		ans += p[i]
		added += 1
	print(ans)


import sys
input = sys.stdin.readline
I = lambda : list(map(int, input().split()))
(t,) = I()
for _ in range(t):
	(n, k) = I()
	l = I()
	an = 0
	if n % 2:
		md = n - n // 2
	else:
		md = n - n // 2 + 1
	ct = 0
	i = n * k - md
	while ct < k:
		an += l[i]
		i -= md
		ct += 1
	print(an)


t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	l = [int(i) for i in input().split()]
	x = 0
	if n % 2 == 0:
		x = n // 2
	else:
		x = n // 2 + 1
	ans = 0
	if x == 1:
		for i in range(k):
			ans += l[x - 1]
			x += n
	else:
		y = n - x + 1
		x = y
		for i in range(k):
			ans += l[n * k - y]
			y += x
	print(ans)


import math
import sys
input = sys.stdin.readline
t = int(input())
for case in range(t):
	(n, k) = [int(x) for x in input().split(' ')]
	a = [int(x) for x in input().split(' ')]
	a.sort()
	s = 0
	for i in range(k):
		for j in range(n - math.ceil(n / 2)):
			a.pop()
		s += a.pop()
	print(s)


for _ in range(int(input())):
	(a, b) = map(int, input().split())
	x = list(map(int, input().split()))
	y = x[::-1]
	c = a // 2 + 1
	d = c
	i = 1
	s = 0
	while i <= b:
		j = c
		s += y[j - 1]
		c += d
		i += 1
	print(s)


import math
for i in range(int(input())):
	(n, k) = map(int, input().split())
	l = list(map(int, input().split()))
	p = int(math.ceil(n / 2))
	if n == 1:
		print(sum(l))
	else:
		s = 0
		l = l[::-1]
		i = 0
		if n % 2 == 0:
			for j in range(p, len(l), p + 1):
				s += l[j]
				i += 1
				if i == k:
					break
		else:
			for j in range(p - 1, len(l), p):
				s += l[j]
				i += 1
				if i == k:
					break
		print(s)
		print()


import math
mod = 1000000007
from sys import stdin, stdout
for abcd in range(int(stdin.readline())):
	(n, k) = map(int, stdin.readline().split())
	li = [0] + list(map(int, stdin.readline().split()))
	ans = 0
	if n % 2 == 1:
		t = n * k
		x = math.ceil(n / 2)
		j = k * (x - 1) + 1
		for i in range(k):
			ans += li[j]
			j += n - x + 1
		print(ans)
	else:
		x = n // 2
		j = k * (x - 1) + 1
		for i in range(k):
			ans += li[j]
			j += n - x + 1
		print(ans)


import math
for _ in range(int(input())):
	(n, k) = [int(i) for i in input().split()]
	arr = [int(i) for i in input().split()]
	arr.sort()
	ans = 0
	val = n - math.ceil(n / 2) + 1
	cnt = 0
	i = len(arr) - val
	while i >= 0:
		if cnt == k:
			break
		ans += arr[i]
		i -= val
		cnt += 1
	print(ans)


for _ in range(int(input())):
	(n, k) = list(map(int, input().split()))
	a = list(map(int, input().split()))
	if n % 2 == 0:
		x = n // 2
	else:
		x = n // 2 + 1
	if x == 1:
		print(sum(a[0:n * k:n]))
	else:
		print(sum(a[k * (x - 1):n * k:n - x + 1]))


import sys
input = sys.stdin.readline
from collections import *
t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	a.sort(reverse=True)
	need = n // 2
	l = []
	i = need
	while len(l) < k:
		l.append(a[i])
		i += need + 1
	print(sum(l))


tests = int(input())
for _ in range(tests):
	(n, k) = map(int, input().split())
	a = [*map(int, input().split())]
	z = n // 2 + 1
	print(sum(a[-z:-z * (k + 1):-z]))


t = int(input())
for i in range(t):
	(n, k) = map(int, input().split())
	l = list(map(int, input().split()))
	m = n // 2
	s = 0
	for j in range(1, k + 1):
		s += l[n * k - j * m - j]
	print(s)


t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	nums = list(map(int, input().split()))
	cutoff = nums[k * ((n - 1) // 2):]
	drop = cutoff[::n - (n - 1) // 2]
	print(sum(drop))


for _ in range(int(input())):
	(n, k) = map(int, input().split(' '))
	first = n // 2
	arr = list(map(int, input().split(' ')))
	if n & 1:
		first += 1
	first = n - first
	ans = 0
	i = n * k - 1
	j = 0
	while j < k:
		i = i - first
		ans += arr[i]
		i -= 1
		j += 1
	print(ans)


t = int(input())
for i in range(t):
	temp = [int(x) for x in input().split()]
	n = temp[0]
	k = temp[1]
	a = [int(x) for x in input().split()]
	if n % 2 == 0:
		m = n // 2
	else:
		m = n // 2 + 1
	total = 0
	for j in range(k):
		x = -(n - m + 1) * (j + 1)
		total += a[x]
	print(total)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	a = list(input().split(' '))
	m = -(-n // 2)
	med = 0
	for i in range(k):
		if n % 2 == 0:
			med = int(a[-m - 1 - i * (m + 1)]) + med
		else:
			med = int(a[-m - i * m]) + med
	print(med)


import sys
reader = (s.rstrip() for s in sys.stdin)
input = reader.__next__
t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	arr = list(map(int, input().split()))
	toLeave = n // 2
	timer = 1
	cnt = k
	ans = 0
	while cnt:
		while timer <= toLeave:
			arr.pop()
			timer += 1
		ans += arr[-1]
		arr.pop()
		cnt -= 1
		timer = 1
	print(ans)


import sys
input = sys.stdin.readline
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	A = list(map(int, input().split()))
	l = (n + 1) // 2 - 1
	B = A[l * k:]
	print(sum((B[i] for i in range(0, len(B), n - l))))


gans = []
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	u = list(map(int, input().split()))
	x = (n - 1) // 2
	u = u[x * k:]
	ans = 0
	for i in range(0, len(u), n - x):
		ans += u[i]
	gans.append(ans)
print(*gans, sep='\n')


import sys
import math
import collections
import bisect

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

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

def get_string():
	return sys.stdin.readline().strip()
for t in range(int(input())):
	(n, k) = get_ints()
	arr = get_list()
	arr.sort(reverse=True)
	ans = 0
	i = n // 2
	count = 0
	while count < k:
		count += 1
		ans += arr[i]
		i += n // 2 + 1
	print(ans)


def solution(n, k, totalArr):
	skip = n // 2
	if k == 1:
		if n % 2 == 0 or n == 1:
			print(totalArr[skip // 2])
		else:
			print(totalArr[skip // 2 + 1])
		return
	if n == 2:
		maxEl = 0
		counter = 0
		for i in range(0, n * k, skip + 1):
			if counter == k:
				break
			maxEl += totalArr[i]
			counter += 1
		print(maxEl)
		return
	if n != 2:
		maxEl = 0
		counter = 0
		for i in range(n * k - 1 - skip, -1, -(skip + 1)):
			if counter == k:
				break
			maxEl += totalArr[i]
			counter += 1
		print(maxEl)
t = int(input())
for _ in range(t):
	(n, k) = list(map(int, input().split()))
	totalArr = list(map(int, input().split()))
	solution(n, k, totalArr)


n = int(input())
for i in range(0, n):
	o = input().rstrip().split(' ')
	p = input().rstrip().split(' ')
	N = int(o[0])
	K = int(o[1])
	if N == 1:
		S = 0
		for j in range(0, len(p)):
			S += int(p[j])
		print(S)
	elif N == 2:
		S = 0
		for j in range(0, len(p), 2):
			S += int(p[j])
		print(S)
	else:
		A = N // 2
		if N % 2 != 0:
			A += 1
		W = 0
		S = len(p) - 1
		ans = 0
		U = 0
		V = 0
		p.reverse()
		if N % 2 == 0:
			R = A + 1
		else:
			R = A
			A = A - 1
		for j in range(0, K):
			ans += int(p[A])
			A = A + R
		print(ans)


def solve(n, k, arr):
	if n % 2 == 0:
		up = n / 2 + 1
		down = n / 2 - 1
	elif n % 2 == 1:
		down = int(n / 2)
		up = n - down
	arr.reverse()
	i = 0
	up = int(up)
	for c in range(1, k * up + 1):
		if c % up == 0:
			i += int(arr[c - 1])
	return i
t = int(input())
for c in range(0, t):
	a = input().split(' ')
	b = input().split(' ')
	print(solve(int(a[0]), int(a[1]), b))


def sumMedian(n, k, a):
	size = n * k
	sum = 0
	i = 0
	point = n // 2
	while i < k:
		sum = sum + a[size - 1 - point]
		point = point + n // 2 + 1
		i = i + 1
	return sum
t = int(input())
for i in range(t):
	(n, k) = input().split()
	n = int(n)
	k = int(k)
	a = [int(x) for x in input().split()]
	print(sumMedian(n, k, a))


for j in range(int(input())):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	sumo = 0
	c = 0
	c1 = n * k
	while c < k:
		c1 = c1 - n // 2
		sumo = sumo + a[c1 - 1]
		c1 = c1 - 1
		c = c + 1
	print(sumo)


import math as m
t = int(input())
for _ in range(t):
	(k, n) = map(int, input().split())
	a = list(map(int, input().split()))
	l = 0
	r = n * k - (k // 2 + 1)
	ans = 0
	while l <= r:
		ans += a[r]
		r -= k // 2 + 1
		l += k - (k // 2 + 1)
	print(ans)


import math
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	m = math.ceil(n / 2)
	r = n - m
	l = m - 1
	q = n * k
	ans = 0
	c = 0
	for i in range(q - 1, -1, -1):
		if r == 0:
			ans += a[i]
			c += 1
			if c >= k:
				break
			r = n - m + 1
		r -= 1
	print(ans)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	array = [int(i) for i in input().split()]
	array.sort(reverse=True)
	step = n // 2 + 1
	x = step - 1
	ans = 0
	counter = 0
	while counter < k:
		ans += array[x]
		x += step
		counter += 1
	print(ans)


from math import ceil
t = int(input())
answers = []
for _ in range(t):
	nk = input().split()
	a = input().split()
	n = int(nk[0])
	m = ceil(n / 2.0)
	k = int(nk[1])
	step = n - m + 1
	medians = []
	for i in range(k):
		medians.append(int(a[-(i + 1) * step]))
	x = sum(medians)
	answers.append(x)
for j in range(t):
	print(answers[j])


for i in range(int(input())):
	(n, k) = map(int, input().split())
	i = list(map(int, input().split()))
	sum = 0
	median = abs(-n // 2)
	if n == 1:
		for p in range(n * k):
			sum = sum + i[p]
	elif n == 2:
		for p in range(0, n * k, 2):
			sum = sum + i[p]
	else:
		for p in range(k * (median - 1), n * k, n - median + 1):
			sum = sum + i[p]
	print(sum)


import math
t = int(input())
for i in range(t):
	(n, k) = map(int, input().split())
	b = list(map(int, input().split()))
	ans = 0
	r = n // 2
	j = n * k - 1
	cnt = 0
	while cnt < k:
		ans += b[j - r]
		cnt += 1
		j -= r + 1
	print(ans)


for _ in range(int(input())):
	(n, k) = input().split()
	(n, k) = (int(n), int(k))
	l = [int(i) for i in input().split()]
	if n % 2 == 0:
		c = n // 2 - 1
	else:
		c = n // 2
	pos = n - c - 1
	t = l[::-1]
	ct = s = 0
	i = pos
	while ct < k:
		ct += 1
		s += t[i]
		i += pos + 1
	print(s)


import math
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	A = list(map(int, input().split()))
	A = A[::-1]
	if n % 2 == 0:
		i = math.ceil(n / 2)
	else:
		i = math.ceil(n / 2) - 1
	ans = 0
	for j in range(k):
		ans += A[i]
		if n % 2 == 0:
			i = i + math.ceil(n / 2) + 1
		else:
			i += math.ceil(n / 2)
	print(ans)


from sys import stdin
input = stdin.readline
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	a = [int(x) for x in input().split()]
	i = max(0, (n - 1) // 2 * k)
	r = a[i:]
	print(sum(r[::len(r) // k]))


n = int(input())
ans = []
for i in range(n):
	(a, b) = list(map(int, input().split()))
	k = list(map(int, input().split()))
	t = 0
	for j in range(0, b):
		t += k[int(a * b - (a // 2 + 1) * (j + 1))]
	ans.append(t)
for i in ans:
	print(i)


t = int(input())
for tests in range(t):
	(n, k) = map(int, input().split())
	A = list(map(int, input().split()))
	dis = n // 2
	SUM = 0
	ind = -1 - dis
	for i in range(k):
		SUM += A[ind]
		ind += -1 - dis
	print(SUM)


t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	if n == 2:
		ans = 0
		for i in range(0, n * k, 2):
			ans += a[i]
		print(ans)
	elif n == 1:
		print(sum(a))
	else:
		ans = 0
		k1 = (n - 1) // 2
		k2 = n - k1
		while len(a) != 0:
			del a[0:k1]
			for i in range(k2):
				if i == k2 - 1:
					ans += a[-1]
				del a[-1]
		print(ans)


import sys

def main():

	def modst(a, s):
		ret = 1
		while s:
			if s % 2:
				ret = ret * a % mod
			a = a * a % mod
			s //= 2
		return ret
	(n, k) = map(int, sys.stdin.readline().split())
	q = sorted(list(map(int, sys.stdin.readline().split())), reverse=True)
	(res, fl, h, i) = (0, 0, n // 2 + 1, n // 2)
	while fl < k:
		fl += 1
		res += q[i]
		i += h
	print(res)
for i in range(int(sys.stdin.readline().strip())):
	main()


from math import ceil

def max_median_sum():
	(s1, s2) = (0, 0)
	for i in range(0, n * k, n):
		s1 += a[i + ceil(n / 2) - 1]
	count = 0
	step = n // 2 + 1
	for i in range(n * k - step, -1, -step):
		s2 += a[i]
		count += 1
		if count == k:
			break
	return max(s1, s2)
for T in range(int(input())):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	print(max_median_sum())


from math import ceil
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	arr = list(map(int, input().split()))
	median_pos = ceil(n / 2)
	j = n * k - 1
	i = 0
	s = 0
	step_size = n - median_pos
	medians = []
	for x in range(k):
		j -= step_size
		s += arr[j]
		medians.append(arr[j])
		j -= 1
	print(s)


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


from math import ceil
for tc in range(int(input())):
	(n, k) = map(int, input().split())
	arr = list(map(int, input().split()))
	m = ceil(n / 2)
	cnt = 0
	for i in range(k):
		for j in range(m, n):
			arr.pop()
		cnt += arr.pop()
	print(cnt)


t = int(input())
for _ in range(t):
	(n, k) = [int(x) for x in input().split()]
	nums = [int(x) for x in input().split()]
	jump = (n + 1) // 2
	n * k - n // 2
	total = 0
	first = (n - 1) // 2 * k
	for i in range(first):
		nums[i] = 0
	for i in range(n * k - 1 - n // 2, -1, -(n // 2 + 1)):
		n = nums[i]
		total += n
	print(total)


t = int(input())
for i in range(t):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	h = 0
	sol = 0
	for i in range(k):
		h = h + n // 2 + 1
		sol = sol + a[-h]
	print(sol)


import sys
import math

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

def get_ints():
	return map(int, sys.stdin.readline().strip().split())
testCases = int(input())
while testCases != 0:
	(n, k) = get_ints()
	a = get_list()
	meanyHead = math.ceil(n / 2)
	meanyHead = n - meanyHead + 1
	county = meanyHead
	answer = 0
	for i in range(k):
		answer += a[-county]
		county += meanyHead
	print(answer)
	testCases -= 1


for t in range(int(input())):
	(n, k) = map(int, input().split())
	k1 = k
	a = list(map(int, input().split()))
	a.sort(reverse=True)
	median = n // 2
	out = 0
	while median < len(a) and k > 0:
		out += a[median]
		median += n // 2 + 1
		k -= 1
	print(out)


for _ in range(int(input())):
	(n, k) = list(map(int, input().split()))
	a = list(map(int, input().split()))
	if n == 1:
		print(sum(a))
	elif n % 2 == 0:
		d = n // 2 - 1
		e = n - d
		f = 0
		sum1 = 0
		for i in range(len(a) - e, -1, -e):
			sum1 += a[i]
			f += 1
			if f == k:
				break
		print(sum1)
	else:
		d = n // 2
		e = n - d
		f = 0
		sum1 = 0
		for i in range(len(a) - e, -1, -e):
			sum1 += a[i]
			f += 1
			if f == k:
				break
		print(sum1)


t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	ali = list(map(int, input().split()))
	q = n // 2 + 1
	mdn = ali[-q::-q]
	print(sum(mdn[:k]))


from math import ceil
t = int(input())
for i in range(t):
	(n, k) = map(int, input().split())
	a = [int(x) for x in input().split()]
	a.sort()
	s = 0
	d = n - ceil(n / 2) + 1
	f = n * k - d
	for j in range(k):
		s += a[f]
		f -= d
	print(s)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	l = list(map(int, input().split()))
	x = (n + 1) // 2
	x = n - x
	x += 1
	s = 0
	m = 0
	for i in range(-x, -(n * k + 1), -x):
		if m == k:
			break
		s += l[i]
		m += 1
	print(s)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	ans = 0
	if n == 1:
		print(sum(a))
		continue
	if n == 2:
		for i in range(0, n * k, 2):
			ans += a[i]
		print(ans)
		continue
	var = n // 2
	var += 1
	c = 0
	cnt = n * k - var
	while cnt > 0 and c < k:
		ans += a[cnt]
		cnt -= var
		c += 1
	print(ans)


import math
for ad in range(int(input())):
	(n, k) = list(map(int, input().split()))
	l = list(map(int, input().split()))
	l.sort()
	l.reverse()
	x = math.ceil(n / 2) + 1 - n % 2
	ans = 0
	for i in range(k):
		ans += l[x * (i + 1) - 1]
	print(ans)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	arr = list(map(int, input().strip().split()))
	total = 0
	ini = n // 2 - 1
	fin = len(arr) - (n // 2 + 1)
	for i in range(k):
		total += arr[fin]
		ini += n // 2 - 1
		fin -= n // 2 + 1
	print(total)


for _ in range(int(input())):
	a = input().split()
	n = int(a[0])
	k = int(a[1])
	A = list(map(int, input().split()))
	sum1 = 0
	z = 0
	A.sort(reverse=True)
	for i in range(n // 2, n * k, n // 2 + 1):
		z += 1
		if z > k:
			break
		sum1 += A[i]
	print(sum1)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	if n <= 2:
		s = 0
		for i in range(0, n * k, n):
			s = s + a[i]
		print(s)
	else:
		s = 0
		mul = n - (n + 2 >> 1)
		for i in range(mul * k, n * k, n + 2 >> 1):
			s = s + a[i]
		print(s)


import math

def solution(n, k, s):
	m = math.ceil(n / 2) - 1
	res = 0
	while s:
		cur = s[:m] + s[-(n - m):]
		s = s[m:-(n - m)]
		res += cur[m]
	return res
t = int(input())
for _ in range(t):
	(n, k) = [int(e) for e in input().split(' ')]
	s = [int(e) for e in input().split(' ')]
	print(solution(n, k, s))


for _ in range(int(input())):
	(n, k) = list(map(int, input().split()))
	a = list(map(int, input().split()))
	x = -(-n // 2)
	sum_ = 0
	c = k
	l = n // 2
	x = n * k - 1
	while c:
		x -= l
		sum_ += a[x]
		x -= 1
		c -= 1
	print(sum_)


from math import ceil
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	array = list(map(int, input().split()))
	mid = ceil(n / 2)
	c = 0
	for i in range(k):
		pos = (i + 1) * (n - mid + 1)
		c += array[-pos]
	print(c)


import math
T = int(input())
for t in range(T):
	(n, k) = list(map(int, input().split(' ')))
	arr = list(reversed(list(map(int, input().split(' ')))))
	result = 0
	g = 0
	for i in range(k):
		if i > 0:
			g += 1
		g += n // 2
		result += arr[g]
	print(result)


from math import ceil as c
t = int(input())
while t > 0:
	t -= 1
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	res = 0
	if n % 2 == 0:
		b = n // 2
	else:
		b = c(n // 2) + 1
	for i in range(k * (b - 1), n * k, n - b + 1):
		res += a[i]
	print(res)


from sys import stdin, stdout
import math, bisect
from collections import Counter, deque, defaultdict
L = lambda : list(map(int, stdin.readline().strip().split()))
M = lambda : map(int, stdin.readline().strip().split())
I = lambda : int(stdin.readline().strip())
S = lambda : stdin.readline().strip()
C = lambda : stdin.readline().strip().split()

def pr(a):
	print(' '.join(list(map(str, a))))

def solve():
	(n, k) = M()
	a = L()
	a.sort(reverse=True)
	ans = 0
	c = 0
	for i in range(n // 2, n * k, n // 2 + 1):
		c += 1
		ans += a[i]
		if c == k:
			break
	print(ans)
for _ in range(I()):
	solve()


import sys
input = sys.stdin.readline
for _ in range(int(input())):
	(n, k) = list(map(int, input().split()))
	arr = list(map(int, input().split()))
	sindex = 0
	endindex = len(arr) - 1
	ans = 0
	while endindex >= sindex:
		endindex -= n // 2
		ans += arr[endindex]
		endindex -= 1
		sindex += (n - 1) // 2
	print(ans)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	sum1 = 0
	x = n / 2
	if x != int(x):
		x = int(x + 1)
	else:
		x = int(x)
	temp = n * k - 1 - (n - x)
	sum1 += a[temp]
	for i in range(1, k):
		sum1 += a[temp - (n - x + 1)]
		temp -= n - x + 1
	print(sum1)


import math
import sys
import itertools
import fractions
wtf = sys.stdin.read()
wtf = wtf.strip().split('\n')
GAP = 2
for t in [wtf[i:i + GAP] for i in range(1, len(wtf), GAP)]:
	(n, k) = map(int, t[0].split())
	A = list(map(int, t[1].split()))
	i = n // 2
	B = []
	s = i + 1
	for j in range(n * k - i - 1, -1, -s):
		B.append(A[j])
	print(sum(B[:k]))


for _ in range(int(input())):
	(n, k) = list(map(int, input().split()))
	A = list(map(int, input().split()))
	ans = 0
	temp = 0
	mid = (n + 1) // 2
	i = n * k
	while k:
		i -= n - mid
		ans += A[i - 1]
		k -= 1
		i -= 1
	print(ans)


t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split())
	l = list(map(int, input().split()))
	l.sort()
	(s, k) = (0, [])
	z = (n - 1) // 2
	if n == 2:
		p = 0
	else:
		p = m
	for i in range(z * m, n * m, n - z):
		k.append(l[i])
		s += l[i]
	if n == 1:
		print(sum(l))
	else:
		print(s)


import math
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	nk = list(map(int, input().split()))
	new = nk[::-1]
	val = math.ceil(n / 2)
	val2 = math.floor(n / 2)
	sumr = 0
	kcnt = 0
	if n % 2 == 0:
		for j in range(val, len(nk), val + 1):
			sumr += new[j]
			kcnt += 1
			if kcnt == k:
				print(sumr)
	else:
		for i in range(val2, len(nk), val2 + 1):
			sumr += new[i]
			kcnt += 1
			if kcnt == k:
				print(sumr)


from math import ceil
t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	l = [int(x) for x in input().split()]
	x = ceil(n / 2)
	ans = 0
	if n == 1:
		ans = sum(l)
	elif n == 2:
		for i in range(0, n * k, 2):
			ans += l[i]
	else:
		if n % 2 == 0:
			i_inc = x - 1
			j_dec = x + 1
		else:
			i_inc = x - 1
			j_dec = x
		(i, j) = (i_inc - 1, n * k - j_dec)
		while i <= j - 1:
			ans += l[j]
			j -= j_dec
			i += i_inc
	print(ans)


for _ in ' ' * int(input()):
	(a, b) = map(int, input().split())
	z = [0] + list(map(int, input().split()))
	k = (a + 1) // 2
	s = 0
	z1 = -1
	i = 1
	j = a * b
	for q in range(b):
		j -= k - a % 2
		s += z[j]
		j -= 1
	print(s)


t = int(input())
for i in range(t):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	sum = 0
	j = k * n
	x = n // 2 + 1
	c = k
	while c > 0:
		c -= 1
		j -= x
		sum += a[j]
	print(sum)


for i in range(int(input())):
	(n, k) = list(map(int, input().split()))
	a = list(map(int, input().split()))
	ans = 0
	if n % 2 == 0:
		x = n // 2 + 1
	else:
		x = n // 2 + 1
	tmp = -x
	for i in range(k):
		ans += a[tmp]
		tmp -= x
	print(ans)


ll = lambda : map(int, input().split())
t = lambda : int(input())
ss = lambda : input()
from math import log10, log2, ceil, factorial as f, gcd
for _ in range(t()):
	(n, k) = ll()
	a = list(ll())
	s = 0
	for i in range(k * (ceil(n / 2) - 1), n * k, n // 2 + 1):
		s += a[i]
	print(s)


import math
for t in range(int(input())):
	(n, k) = map(int, input().split())
	li = list(map(int, input().split()))
	li.reverse()
	j = math.ceil(n / 2)
	s = 0
	i = n - j
	for _ in range(0, k):
		s = s + li[i]
		if n % 2 == 0:
			i = i + j + 1
		else:
			i = i + j
	print(s)


import math
for i in range(int(input())):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	meanindex = math.ceil(n / 2)
	meanindex = n - meanindex + 1
	counter = meanindex
	ans = 0
	for i in range(k):
		ans += a[-counter]
		counter += meanindex
	print(ans)


import math
for _ in range(int(input())):
	(n, k) = [int(x) for x in input().split()]
	arr = [int(x) for x in input().split()]
	c = math.ceil(n / 2)
	rem = n - c
	ind = n * k - rem
	ans = 0
	for i in range(k):
		ans += arr[ind - 1]
		ind = ind - rem - 1
	print(ans)


from math import ceil
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	l = list(map(int, input().split()))
	ans = 0
	if n == 1:
		ans = sum(l)
	elif n == 2:
		i = 0
		while k:
			ans += l[i]
			i += 2
			k -= 1
	else:
		p = (n - 1) // 2
		i = k * p
		while k:
			ans += l[i]
			i += n - p
			k -= 1
	print(ans)


import sys
import math
input = sys.stdin.readline
t = int(input())
for w in range(t):
	(n, k) = (int(i) for i in input().split())
	l = [int(i) for i in input().split()]
	med = math.ceil(n / 2) - 1
	c = 0
	r = n - med + 1
	j = n * k - r + 1
	s = 0
	while c < k:
		s += l[j]
		j -= r - 1
		c += 1
	print(s)


import sys, itertools
tc = int(sys.stdin.readline())
for _ in range(tc):
	(n, k) = map(int, sys.stdin.readline().split())
	arr = list(map(int, sys.stdin.readline().split()))
	temp = n // 2 if n % 2 == 0 else n // 2 + 1
	interval = n - (temp - 1)
	res = 0
	for j in range((temp - 1) * k, len(arr), interval):
		res += arr[j]
	print(res)


import math
n = int(input())
for i in range(n):
	(a, b) = [i for i in map(int, input().split())]
	size = a * b
	arr = list(map(int, input().split()))
	m = math.ceil(a / 2)
	sum = 0
	x = a * b - 1
	z = 0
	if a == 2:
		for j in range(b):
			sum += arr[2 * j]
	else:
		for k in range(b):
			arr1 = []
			for l in range(m - 1):
				arr1.append(arr[z])
				z += 1
			for j in range(a - m + 1):
				arr1.append(arr[x - (a - m + 1) + 1 + j])
			sum += arr1[m - 1]
			x -= a - m + 1
	print(sum)


for y in range(int(input())):
	(n, k) = map(int, input().split())
	lst = list(map(int, input().split()))
	if n == 1:
		print(sum(lst))
	elif n == 2:
		summ = 0
		for i in range(0, n * k, 2):
			summ += lst[i]
		print(summ)
	else:
		str = (n + 1) // 2 - 1
		end = n - str
		summ = 0
		for i in range(str * k, n * k, end):
			summ += lst[i]
		print(summ)


import math
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	sum = 0
	mid = math.ceil(n / 2)
	mid = n - mid + 1
	n *= k
	for i in range(k):
		n -= mid
		sum += a[n]
	print(sum)


from collections import Counter
import math
import sys
import heapq
from bisect import bisect, bisect_left, bisect_right

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

def INT():
	return int(input())

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

def LIST(N=None):
	return list(MAP()) if N is None else [INT() for i in range(N)]

def mod():
	return 10 ** 9 + 7
for i in range(INT()):
	(n, k) = MAP()
	a = LIST()
	ans = 0
	for i in range(n * k - n // 2, -1, -(n // 2 + 1)):
		if k == 0:
			break
		k -= 1
		ans += a[i - 1]
	print(ans)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	s = 0
	if n == 1:
		print(sum(a))
	elif n == 2:
		print(sum([a[i] for i in range(n * k) if i % 2 == 0]))
	else:
		while len(a) > 0:
			s += a[-(n - (n - 1) // 2)]
			a = a[(n - 1) // 2:-(n - (n - 1) // 2)]
		print(s)


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


import math
t = int(input())

def solve(n, k, nums):
	ngt = n - math.ceil(n / 2)
	c = 0
	i = n * k - 1 - ngt
	res = 0
	while c < k:
		res += nums[i]
		i -= ngt + 1
		c += 1
	print(res)
for _ in range(t):
	(n, k) = list(map(int, input().split()))
	nums = list(map(int, input().split()))
	solve(n, k, nums)


import math as mt
t = int(input())
i = 0
while i < t:
	(n, k) = map(int, input().split())
	arr = list(map(int, input().split()))
	count = 0
	p = 0
	if k == 1:
		count = arr[mt.ceil(n / 2) - 1]
	elif n != 2:
		for m in range(len(arr) - 1 - mt.floor(n / 2), -1, -(mt.floor(n / 2) + 1)):
			count += arr[m]
			p += 1
			if p == k:
				break
	else:
		for m in range(len(arr) - 2, -1, -2):
			count += arr[m]
			p += 1
			if p == k:
				break
	print(count)
	i += 1


t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	j = n - int(n - 1) // 2
	ans = 0
	last = n * k - j
	for i in range(k - 1, -1, -1):
		ans += a[last]
		last = last - j
	print(ans)


import math
t = int(input())
for i in range(t):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	a.sort()
	a.reverse()
	cnt = 0
	val = n - math.ceil(n / 2)
	j = val
	sum1 = 0
	while cnt < k:
		sum1 += a[j]
		j += val + 1
		cnt += 1
	print(sum1)


from math import *
t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	arr = [int(i) for i in input().split()]
	d = n // 2 + 1
	(s, c) = (0, 0)
	for i in range(n * k - d, -1, -d):
		s = s + arr[i]
		c = c + 1
		if c == k:
			print(s)
			break


for _ in range(0, int(input())):
	(n, k) = map(int, input().split())
	v = sorted(map(int, input().split()))[::-1]
	d = n // 2
	s = v[d::d + 1][:k]
	print(sum(s))


for _ in range(int(input())):
	(n, k) = [int(x) for x in input().split()]
	vals = [int(x) for x in input().split()][::-1]
	sums = 0
	curr = n // 2
	for i in range(k):
		sums += vals[curr]
		curr += n // 2 + 1
	print(sums)


import sys
import math

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

def str_arr():
	return list(map(str, sys.stdin.readline().split()))

def input():
	return sys.stdin.readline()

def out(x):
	return sys.stdout.write(str(x))
for _ in range(int(input())):
	(n, m) = int_arr()
	arr = int_arr()
	ans = 0
	j = n * m - 1
	if n % 2 == 0:
		diff_b = n // 2 + 1
	else:
		diff_b = n // 2 + 1
	for l in range(m):
		j -= diff_b
		ans += arr[j + 1]
	print(ans)


import sys
import math
from collections import defaultdict, Counter
input = sys.stdin.readline

def print(x):
	sys.stdout.write(str(x) + '\n')
t = int(input())
for i in range(t):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	ans = 0
	c = 0
	d = n - (n + 1) // 2 + 1
	for j in range(n * k - d, -1, -d):
		ans += a[j]
		c += 1
		if c == k:
			break
	print(ans)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	x = n // 2
	if n % 2 != 0:
		x += 1
	t = n - x + 1
	j = n * k - t
	c = 0
	while k > 0:
		c += a[j]
		j -= t
		k -= 1
	print(c)


from sys import stdin, stdout
t = int(stdin.readline())
for _ in range(t):
	(n, k) = map(int, stdin.readline().split())
	arr = list(map(int, stdin.readline().split()))
	i = 0
	j = len(arr) - 1
	cost = 0
	while i < k:
		j -= n // 2
		cost += arr[j]
		i += 1
		j -= 1
	print(cost)


for _ in [0] * int(input()):
	(n, m) = map(int, input().split())
	r = [*map(int, input().split())]
	print(sum(r[(n // 2 + n % 2 - 1) * m::n // 2 + 1]))


import math
num = int(input())
for i in range(num):
	arr = input().split(' ')
	m = int(arr[0])
	n = int(arr[1])
	arr1 = input().split(' ')
	arr1 = list(map(int, arr1))
	l = m - math.ceil(m / 2) + 1
	s = arr1[-l::-l]
	print(sum(s[:n]))


from sys import stdin
from collections import defaultdict, Counter
from math import ceil

def iinput():
	return int(stdin.readline())

def minput():
	return map(int, stdin.readline().split())

def linput():
	return list(map(int, stdin.readline().split()))
t = iinput()
while t:
	t -= 1
	(n, k) = minput()
	a = linput()
	med = 0
	m = ceil(n / 2)
	i = (k - 1) * n - 1 + m
	d = n * k - i
	while k:
		med += a[i]
		i -= d
		k -= 1
	print(med)


import math
t = int(input())
for i in range(t):
	(n, k) = map(int, input().split())
	ar = list(map(int, input().split()))
	med = math.ceil(n / 2)
	prev = (med - 1) * k
	ans = 0
	for i in range(prev, n * k, n - med + 1):
		ans += ar[i]
	print(ans)


t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	arr = [int(j) for j in input().split()]
	ans = 0
	jump = n // 2 + 1
	count = 0
	for i in range(n * k - jump, -1, -jump):
		if count == k:
			break
		count += 1
		ans += arr[i]
	print(ans)


from math import ceil, floor
t = int(input())
for k in range(t):
	(n, k) = map(int, input().split())
	s = [int(i) for i in input().split()]
	s.reverse()
	ans = 0
	f = floor(n / 2)
	for i in range(k):
		ans += s[f]
		f += floor(n / 2) + 1
	print(ans)


t = int(input())
for _ in range(t):
	(n, k) = [int(x) for x in input().split()]
	l = [int(x) for x in input().split()]
	i = n * k - 1
	ans = 0
	if n / 2 - int(n / 2) > 0:
		count = int(n - int(n / 2 + 1))
	else:
		count = int(n - n / 2)
	loop = 0
	while loop < k:
		loop += 1
		i -= count
		i = int(i)
		ans += l[i]
		i -= 1
	print(ans)


def solve(n, k, a):
	sum = 0
	ind = (n - 1) // 2
	for i in range(k * ind, len(a), n - ind):
		sum += a[i]
	print(sum)
rep = int(input())
for _ in range(rep):
	a = input().split()
	n = int(a[0])
	k = int(a[1])
	arr = [int(x) for x in input().split()]
	solve(n, k, arr)


t = int(input())
for i in range(t):
	(n, k) = input().split()
	n = int(n)
	k = int(k)
	a = list(map(int, input().split()))
	a.sort()
	sum = 0
	for j in range(k):
		sum += a[-(n // 2 + 1) * (j + 1)]
	print(sum)


t = int(input())
ans = []
for _ in range(t):
	(n, k) = [int(x) for x in input().split()]
	a = [int(x) for x in input().split()]
	u = (n >> 1) + 1
	ret = 0
	nk = len(a) - u
	for i in range(k):
		ret += a[nk - i * u]
	ans.append(str(ret))
print('\n'.join(ans))


from sys import stdin
input = lambda : stdin.readline().strip()
for _ in range(int(input())):
	(n, k) = [int(i) for i in input().split()]
	lst = [int(i) for i in input().split()]
	if n == 2:
		d = n // 2
		sum1 = 0
		lst1 = []
		nd = 0
		for i in range(0, n * k):
			if nd == n:
				nd = 0
				sum1 += lst1[d - 1]
				lst1 = []
			lst1.append(lst[i])
			nd += 1
		if nd == n:
			sum1 += lst1[d - 1]
		print(sum1)
	elif n % 2 == 0:
		d = n // 2
		dd = n - d + 1
		d = d - 1
		nd = 0
		pp = 0
		sum1 = 0
		i = n * k - 1
		while i > pp:
			nd += 1
			if nd == dd:
				sum1 += lst[i]
				nd = 0
				pp = pp + d
			i -= 1
		print(sum1)
	else:
		d = n // 2
		dd = n - d
		nd = 0
		pp = -1
		sum1 = 0
		i = n * k - 1
		while pp < i:
			nd += 1
			if nd == dd:
				sum1 += lst[i]
				nd = 0
				pp = pp + d
			i -= 1
		print(sum1)


import math
for _ in range(int(input())):
	data = list(map(int, input().split()))
	(n, k) = (data[0], data[1])
	numbers = list(map(int, input().split()))
	median = math.ceil(n / 2) - 1
	total = 0
	if n <= 2:
		for i in range(k):
			total += numbers[median + n * i]
		print(total)
	else:
		for i in range(1, k + 1):
			total += numbers[-i * (n - median)]
		print(total)


import math

def median_idx(n):
	return n // 2 + n % 2 - 1

def run():
	t = int(input())
	for _ in range(t):
		(n, k) = list(map(int, input().split()))
		nk = list(map(int, input().split()))
		sz = len(nk)
		midx = median_idx(n)
		if midx == 0:
			total_median = 0
			for i in range(k):
				total_median += nk[i * n]
			print(total_median)
			continue
		total_median = 0
		sleft = midx
		sright = n - midx
		for i in range(1, k + 1):
			total_median += nk[sz - i * sright]
		print(total_median)
run()


import math
t = int(input())
for i in range(t):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	c = n * k
	ans = 0
	for j in range(1, k + 1):
		ind = j * (-(n // 2) - 1)
		ans += a[ind]
	print(ans)


test_cases = int(input())
for test_case in range(test_cases):
	(n, k) = list(map(int, input().split()))
	a = list(map(int, input().split()))
	ans = 0
	if n % 2 == 0:
		m = n // 2
		m = n - m + 1
	else:
		m = n // 2 + 1
		m = n - m + 1
	j = 1
	count = 0
	for i in reversed(a):
		if j % m == 0:
			ans += i
			count += 1
		if count == k:
			break
		j += 1
	print(ans)


for i in range(int(input())):
	(n, k) = map(int, input().split())
	arr = list(map(int, input().split()))
	arr.sort(reverse=True)
	n = n - 1
	m1 = n // 2
	m2 = n + 1 - m1
	(m1, m2) = (min(m1, m2), max(m1, m2))
	s = 0
	for i in range(m2 - 1, k * m2, m2):
		s += arr[i]
	print(s)


from math import ceil
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	l = list(map(int, input().split()))
	ans = 0
	x = ceil(n / 2)
	for i in range(k):
		ans += l[(i + 1) * -(n - x + 1)]
	print(ans)


def main():
	for case in range(int(input())):
		(n, k) = map(int, input().split())
		ar = list(map(lambda x: int(x), input().split()))
		a = n // 2
		ff = len(ar) - 1
		ans = 0
		for i in range(k):
			ff = ff - a
			ans = ans + ar[ff]
			ff = ff - 1
		print(ans)
main()


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	ans = 0
	if n == 1:
		print(sum(a))
	elif n == 2:
		for i in range(0, n * k, +2):
			ans += a[i]
		print(ans)
	else:
		ans = 0
		x = n // 2
		c = 0
		for i in range(n * k - x - 1, -1, -x):
			if c == k:
				break
			ans += a[i - c]
			c += 1
		print(ans)


import sys
import math
import collections
import operator as op
from collections import deque
from math import gcd, inf, sqrt, pi, cos, sin, ceil, log2, floor
from bisect import bisect_right, bisect_left, bisect
from functools import reduce
from sys import stdin, stdout, setrecursionlimit
setrecursionlimit(2 ** 20)

def ncr(n, r):
	r = min(r, n - r)
	numer = reduce(op.mul, range(n, n - r, -1), 1)
	denom = reduce(op.mul, range(1, r + 1), 1)
	return numer // denom

def prime_factors(n):
	i = 2
	factors = []
	while i * i <= n:
		if n % i:
			i += 1
		else:
			n //= i
			factors.append(i)
	if n > 1:
		factors.append(n)
	return list(factors)

def isPowerOfTwo(x):
	return x and (not x & x - 1)
MOD = 1000000007
PMOD = 998244353
N = 10 ** 9 + 7
LOGN = 30
T = 1
T = int(stdin.readline())
for _ in range(T):
	(n, k) = list(map(int, stdin.readline().rstrip().split()))
	a = list(map(int, stdin.readline().rstrip().split()))
	a1 = []
	a2 = []
	a3 = []
	for i in range(k):
		a1.append(a[i * n:i * n + n])
	for i in range(n):
		a2.append(a[i * k:i * k + k])
	a2 = [[a2[j][i] for j in range(len(a2))] for i in range(len(a2[0]))]
	ans1 = 0
	ans2 = 0
	for i in a1:
		ans1 += i[ceil(n / 2) - 1]
	for i in a2:
		ans2 += i[ceil(n / 2) - 1]
	a.reverse()
	ix = n - ceil(n / 2)
	ans3 = 0
	for i in range(ix, n * k - (ceil(n / 2) - 1) * k, ix + 1):
		ans3 += a[i]
	print(max(ans1, ans2, ans3))


t = int(input())
for i in range(t):
	(n, k) = map(int, input().split())
	l = list(map(int, input().split()))
	s = 0
	e = 0
	t = 0
	new = l[::-1]
	if k == 1:
		if n % 2 == 0:
			print(l[n // 2 - 1])
		else:
			print(l[n // 2])
	elif n == 2:
		for i in range(len(l)):
			if i % 2 == 0:
				e += l[i]
		print(e)
	else:
		for i in range(k):
			if n % 2 != 0:
				if i == 0:
					s += new[n // 2]
				else:
					s += new[n // 2 + i * (n // 2) + i]
			else:
				s += new[n // 2 + t + i]
				t += n // 2
		print(s)


t = int(input())
while t > 0:
	(n, k) = map(int, input().split())
	arr = list(map(int, input().split()))
	x = n * k - 1
	sum = 0
	while k > 0:
		x -= int(n / 2)
		sum += arr[x]
		x -= 1
		k -= 1
	print(sum)
	t -= 1


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	daf = list(map(int, input().split()))
	daf.sort()
	has = 0
	for i in range(k):
		has += daf[-(i + 1) * (n // 2 + 1)]
	print(has)


from math import ceil
t = int(input())
for T in range(t):
	(n, k) = [int(x) for x in input().split()]
	l = [int(x) for x in input().split()]
	ind = ceil(n / 2)
	ind -= 1
	lind = 0
	l1 = [[] for x in range(k)]
	for i in range(k):
		for j in range(ind):
			l1[i].append(l[lind])
			lind += 1
	for i in range(k):
		for j in range(ind, n):
			l1[i].append(l[lind])
			lind += 1
	ans = 0
	for i in range(k):
		ans += l1[i][ind]
	print(ans)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	a.sort()
	sm = 0
	i = 0
	j = n * k
	ct = n // 2 + 1
	while i < j:
		for l in range(ct):
			j -= 1
		for l in range(n - ct):
			i += 1
		sm += a[j]
	print(sm)


from math import *
t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	med = ceil(n / 2)
	med = n - med
	med += 1
	su = 0
	count = 0
	for i in range(n * k - med, -1, -med):
		su += a[i]
		count += 1
		if count == k:
			break
	print(su)


import math
t = int(input())
for q in range(t):
	(n, k) = list(map(int, input().split()))
	lst = list(map(int, input().split()))
	g = n - math.ceil(n / 2)
	i = n * k - 1
	sums = 0
	c = 0
	while c < k and i >= 0:
		i = i - g
		sums += lst[i]
		i = i - 1
		c = c + 1
	print(sums)


R = lambda : [*map(int, input().split())]
for _ in [0] * R()[0]:
	(n, k) = R()
	print(sum(R()[(n - 1) // 2 * k::n // 2 + 1]))


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	mid = (n + 1) // 2
	right = n - mid + 1
	i = right
	ans = 0
	for j in range(k):
		ans += a[-i]
		i += right
	print(ans)


t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	s = 0
	m = (n + 1) // 2
	b = k
	x = n - m
	j = n * k - x - 1
	while b:
		s += a[j]
		j -= x + 1
		b -= 1
	print(s)


import math
t = int(input())
for x in range(t):
	(n, k) = map(int, input().split())
	arr = input().split()
	median_pos = math.ceil(n / 2) - 1
	start_pos = median_pos * k
	res = 0
	for y in range(k):
		add = int(arr[start_pos + y * (n - median_pos)])
		res += add
	print(res)


inp = lambda : list(map(int, input().split(' ')))
for _ in range(int(input())):
	(n, k) = inp()
	a = inp()
	sum = 0
	f = n // 2 + 1
	for j in range(1, k + 1):
		sum += a[-f * j]
	print(sum)


import bisect
from itertools import accumulate
import os
import sys
import math
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))

def input():
	return sys.stdin.readline().rstrip('\r\n')
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	a = sorted(list(map(int, input().split())))
	a = a[::-1]
	sumi = 0
	j = n // 2 + 1
	i = n // 2
	while k > 0:
		sumi += a[i]
		i += j
		k -= 1
	print(sumi)


for tt in range(int(input())):
	(n, k) = map(int, input().split())
	arr = list(map(int, input().split()))
	if n == 2:
		cnt = 0
		for i in range(0, n * k, 2):
			cnt += arr[i]
		print(cnt)
		continue
	mid = n // 2 + 1
	end = n * k - mid
	cnt = 0
	for i in range(k):
		cnt += arr[end]
		end -= mid
	print(cnt)


t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	l = list(map(int, input().split()))
	median = n // 2
	if n % 2 == 1:
		median += 1
	count = 1
	s = 0
	len = n * k
	if n % 2 == 0:
		i = median
		while count <= k:
			s += l[len - 1 - i]
			i += median + 1
			count += 1
		print(s)
	else:
		i = median - 1
		median -= 1
		while count <= k:
			s += l[len - 1 - i]
			i += median + 1
			count += 1
		print(s)


def main():
	t = int(input())
	for _ in range(t):
		(n, k) = map(int, input().split())
		s = list(map(int, input().split()))
		ss = 0
		kk = n // 2 + 1
		for i in range(k):
			ss += s[-kk * (i + 1)]
		print(ss)
main()


from math import floor
for _ in range(int(input())):
	(n, k) = map(int, input().split(' '))
	arr = [int(num) for num in input().split(' ')]
	t = n / 2
	f = round(t)
	if t - floor(t) == 0.5:
		if floor(t) % 2 == 0:
			f = f + 1
	x = n - f + 1
	p = k * n
	ans = 0
	for i in range(1, k + 1):
		ans = ans + arr[p - x * i]
	print(ans)


t = int(input())
while t:
	t -= 1
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	s = 0
	j = n // 2 + 1
	nn = k
	for i in range(n * k - 1, -1, -1):
		if j == 1:
			s += a[i]
			nn -= 1
			j = n // 2 + 1
		elif nn == 0:
			break
		else:
			j -= 1
	print(s)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	array = list(map(int, input().split()))
	if n & 1:
		left = int(n / 2)
		right = n - left
	else:
		left = int(n / 2) - 1
		right = n - left
	index_k = 0
	l = len(array)
	acc = 0
	s = []
	for i in range(k):
		s.extend(array[left * index_k:left * index_k + left])
		s.extend(array[l - right * (i + 1):l - right * (i + 1) + right])
		if not n & 1:
			acc += s[int(len(s) / 2 - 1)]
		else:
			acc += s[int(len(s) / 2)]
		index_k += 1
		s.clear()
	print(acc)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	total = 0
	a.reverse()
	t = n - (n + 1) // 2 + 1
	for i in range(1, k + 1):
		total += a[t * i - 1]
	print(total)


import sys

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

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

def input():
	return sys.stdin.readline().strip()
for _ in range(int(input())):
	(n, k) = get_ints()
	a = get_array()
	tot = 0
	i = len(a) - 1
	sumi = 0
	ans = 0
	rem = n // 2
	while True:
		tot += 1
		if tot - 1 == rem:
			ans += a[i]
			sumi += 1
			tot = 0
		i -= 1
		if sumi == k:
			break
	print(ans)


import math
import os
import random
import re
import string
from sys import *
from collections import *

def bs(arr, x, l, r):
	if l <= r:
		mid = (r + l) // 2
		if arr[mid] == x:
			return mid
		elif arr[mid] > x:
			return bs(arr, x, l, mid - 1)
		else:
			return bs(arr, x, mid + 1, r)
	else:
		return -1

def solve():
	for _ in range(int(input())):
		(n, k) = map(int, stdin.readline().strip().split())
		l = list(map(int, stdin.readline().strip().split()))
		l.sort(reverse=True)
		n1 = n // 2
		j = n1
		c = 0
		for i in range(k):
			c += l[j]
			j += n1 + 1
		print(c)
solve()


t = int(input())
for hh in range(0, t):
	(n, k) = [int(x) for x in input().split()]
	a = [int(x) for x in input().split()]
	if n == 1:
		ans = sum(a)
		print(ans)
	elif n == 2:
		ans = 0
		for j in range(0, n * k):
			if j % 2 == 0:
				ans += a[j]
		print(ans)
	else:
		if n % 2 == 1:
			midd = n // 2
		else:
			midd = (n - 1) // 2
		prv = midd * k
		strt = prv
		ans = 0
		while strt < n * k:
			ans += a[strt]
			rem = n - midd
			strt += rem
		print(ans)


import sys
from functools import lru_cache, cmp_to_key
from heapq import merge, heapify, heappop, heappush, nsmallest
from math import ceil, floor, gcd, fabs, factorial, fmod, sqrt, inf, log
from collections import defaultdict as dd, deque, Counter as C
from itertools import combinations as comb, permutations as perm
from bisect import bisect_left as bl, bisect_right as br, bisect
from time import perf_counter
from fractions import Fraction
from decimal import Decimal
mod = pow(10, 9) + 7
mod2 = 998244353

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

def out(var):
	sys.stdout.write(str(var) + '\n')

def outa(*var, end='\n'):
	sys.stdout.write(' '.join(map(str, var)) + end)

def l():
	return list(sp())

def sl():
	return list(ssp())

def sp():
	return map(int, data().split())

def ssp():
	return map(str, data().split())

def l1d(n, val=0):
	return [val for i in range(n)]

def l2d(n, m, val=0):
	return [l1d(n, val) for j in range(m)]
for _ in range(int(data())):
	(n, k) = sp()
	arr = deque(l())
	answer = 0
	temp = n >> 1
	while arr:
		for i in range(temp):
			arr.pop()
		if arr:
			answer += arr.pop()
		for i in range(temp - (1, 0)[n & 1]):
			arr.popleft()
	out(answer)


import os
import sys
from math import *
from collections import *
from bisect import *
from io import BytesIO, IOBase

def vsInput():
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
ALPHA = 'abcdefghijklmnopqrstuvwxyz/'
M = 1000000007
EPS = 1e-06

def Ceil(a, b):
	return a // b + int(a % b > 0)

def value():
	return tuple(map(int, input().split()))

def array():
	return [int(i) for i in input().split()]

def Int():
	return int(input())

def Str():
	return input()

def arrayS():
	return [i for i in input().split()]
for _ in range(Int()):
	(n, k) = value()
	a = array()
	a.sort(reverse=True)
	jump = n // 2 + 1
	ans = []
	for i in range(0, n * k, jump):
		ans.append(a[i + jump - 1])
		if len(ans) == k:
			break
	print(sum(ans))


import math

def maxSumOfMedian(n, k, li):
	length = len(li)
	median = math.ceil(n / 2)
	start = (median - 1) * k
	sum = li[start]
	for i in range(1, k):
		sum += li[start + (n - median + 1) * i]
	return sum
t = int(input())
while t:
	(n, k) = map(int, input().split())
	li = list(map(int, input().split()))
	print(maxSumOfMedian(n, k, li))
	t -= 1


import math
t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	A = list(map(int, input().split()))
	f = n - math.ceil(n / 2)
	pos = n * k - 1 - f
	ans = A[pos]
	for _ in range(k - 1):
		pos -= f + 1
		ans += A[pos]
	print(ans)


t = int(input())
while t != 0:
	t -= 1
	(n, k) = map(int, input().split())
	fg = list(map(int, input().split()))
	sumi = 0
	for i in range(0, k):
		sumi += fg[-(n // 2 + 1) * (i + 1)]
	print(sumi)


for i in range(int(input())):
	(n, k) = map(int, input().split())
	A = list(map(int, input().split()))
	A.reverse()
	c = []
	w = n // 2
	for i in range(k):
		c.append(A[w])
		w += n // 2 + 1
	print(sum(c))


t = int(input())
for x in range(t):
	(n, k) = map(int, input().split())
	arreglo = list(map(int, input().split()))
	if n == 1:
		print(sum(arreglo))
	else:
		suma = 0
		inicial = n // 2 + 1
		shift = inicial
		for m in range(k):
			suma = suma + arreglo[-inicial]
			inicial = inicial + shift
		print(suma)


def max_median_sum():
	s1 = 0
	count = 0
	step = n // 2 + 1
	for i in range(n * k - step, -1, -step):
		s1 += a[i]
		count += 1
		if count == k:
			break
	return s1
for T in range(int(input())):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	print(max_median_sum())


import math
t = int(input())

def solu():
	(n, k) = map(int, input().split(' '))
	arr = list(map(int, input().split(' ')))
	med_index = math.ceil(n / 2) - 1
	nums_med = med_index * k
	right = arr[nums_med:]
	right_chapter = n - med_index
	summ = 0
	for i in range(len(right)):
		if i % right_chapter == 0:
			summ += right[i]
	print(summ)
for _ in range(t):
	solu()


for i in range(int(input())):
	(n, m) = map(int, input().split())
	a = list(map(int, input().split()))
	s = 0
	if n == 1:
		print(sum(a))
	elif n == 2:
		b = a[0::2]
		print(sum(b))
	else:
		p = (n - 1) // 2
		i = m * p
		for k in range(m):
			s += a[i]
			i += n - p
		print(s)


import math
t = int(input())
for r in range(t):
	(n, k) = list(map(int, input().split()))
	arr = list(map(int, input().split()))
	arr.sort()
	p = math.floor(n / 2)
	sum = 0
	lpointer = 0
	rpointer = n * k
	for f in range(k):
		lpointer += p - 1
		rpointer -= p + 1
		sum += arr[rpointer]
	print(sum)


t = int(input())
for i in range(t):
	(n, k) = map(int, input().split())
	l = list(map(int, input().split()))
	ans = 0
	s = 0
	m = n // 2
	for i in range(n * k - 1, -1, -1):
		if k == 0:
			break
		if s == m:
			ans += l[i]
			s = 0
			k -= 1
		else:
			s += 1
	print(ans)


t = int(input())
for ww in range(t):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	med = (n - 1) // 2
	ans = 0
	for i in range(med * k, n * k, n - med):
		ans += a[i]
	print(ans)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	arr = list(map(int, input().split()))
	matrix = [[0 for i in range(n)] for j in range(k)]
	if n % 2 == 0:
		final_index = n // 2 - 1
	else:
		final_index = n // 2
	index = len(arr) - 1
	for i in range(k - 1, -1, -1):
		for j in range(n - 1, final_index - 1, -1):
			matrix[i][j] = arr[index]
			index -= 1
	sol = 0
	for i in matrix:
		sol += i[final_index]
	print(sol)


from sys import stdin, stdout
input = stdin.readline
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	div = n // 2 + 1
	index = n * k - div
	count = k
	ans = 0
	while count > 0 and index >= 0:
		ans += a[index]
		index -= div
		count -= 1
	stdout.write(str(ans) + '\n')


import math
a = int(input())
for i in range(a):
	(b, c) = map(int, input().split())
	d = list(map(int, input().split()))
	d.sort(reverse=True)
	e = 0
	f = b - math.ceil(b / 2)
	for j in range(f, c * (f + 1), f + 1):
		e += d[j]
	print(e)


import sys
from array import array
import typing as Tp

def input():
	return sys.stdin.buffer.readline().decode('utf-8')

def output(*args):
	sys.stdout.buffer.write(('\n'.join(map(str, args)) + '\n').encode('utf-8'))

def main():
	t = int(input())
	ans_a = [''] * t
	for ti in range(t):
		(n, k) = map(int, input().split())
		a = list(map(int, input().split()))
		left = (n + 1 >> 1) - 1
		right = n - left - 1
		(i, j) = (0, n * k - 1)
		ans = 0
		for _ in range(k):
			j -= right
			ans += a[j]
			j -= 1
		ans_a[ti] = str(ans)
	output(*ans_a)
main()


import sys
import math
import itertools
import functools
import collections
import operator
import fileinput
import copy
import string
ORDA = 97

def ii():
	return int(input())

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

def li():
	return [int(i) for i in input().split()]

def lcm(a, b):
	return abs(a * b) // math.gcd(a, b)

def revn(n):
	return str(n)[::-1]

def dd():
	return collections.defaultdict(int)

def ddl():
	return collections.defaultdict(list)

def sieve(n):
	if n < 2:
		return list()
	prime = [True for _ in range(n + 1)]
	p = 3
	while p * p <= n:
		if prime[p]:
			for i in range(p * 2, n + 1, p):
				prime[i] = False
		p += 2
	r = [2]
	for p in range(3, n + 1, 2):
		if prime[p]:
			r.append(p)
	return r

def divs(n, start=2):
	r = []
	for i in range(start, int(math.sqrt(n) + 1)):
		if n % i == 0:
			if n / i == i:
				r.append(i)
			else:
				r.extend([i, n // i])
	return r

def divn(n, primes):
	divs_number = 1
	for i in primes:
		if n == 1:
			return divs_number
		t = 1
		while n % i == 0:
			t += 1
			n //= i
		divs_number *= t

def prime(n):
	if n == 2:
		return True
	if n % 2 == 0 or n <= 1:
		return False
	sqr = int(math.sqrt(n)) + 1
	for d in range(3, sqr, 2):
		if n % d == 0:
			return False
	return True

def convn(number, base):
	new_number = 0
	while number > 0:
		new_number += number % base
		number //= base
	return new_number

def cdiv(n, k):
	return n // k + (n % k != 0)

def ispal(s):
	for i in range(len(s) // 2 + 1):
		if s[i] != s[-i - 1]:
			return False
	return True
for _ in range(ii()):
	(n, k) = mi()
	arr = li()
	ans = 0
	if n < 3:
		ans = sum(arr[::n])
	else:
		j = 0
		i = n * k - math.ceil((n + 1) / 2)
		while j < k:
			ans += arr[i]
			i -= math.ceil((n + 1) / 2)
			j += 1
	print(ans)


from math import ceil
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	if n == 1:
		print(sum(a))
		continue
	elif n == 2:
		print(sum((a[i] for i in range(0, n * k, 2))))
		continue
	else:
		c = ceil(n / 2)
		print(sum((a[i] for i in range((c - 1) * k, n * k, n - c + 1))))


for _ in range(int(input())):
	(n, k) = list(map(int, input().split()))
	arr = list(map(int, input().split()))
	arr.sort()
	d = n - (n - 1) // 2
	ans = 0
	for i in range((n - 1) // 2 * k, n * k, d):
		ans += arr[i]
	print(ans)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	step = n // 2 + 1
	pos = n * k - step
	count = k
	ans = 0
	while count:
		ans += a[pos]
		pos -= step
		count -= 1
	print(ans)


T = int(input())
for t in range(T):
	(n, k) = [int(k) for k in input().split()]
	arr = sorted([int(k) for k in input().split()])
	total = 0
	for i in range(k):
		total += arr[len(arr) - (n // 2 + 1) * (i + 1)]
	print(total)


for i in range(int(input())):
	(n, m) = map(int, input().split())
	s = list(map(int, input().split()))
	s.reverse()
	c = []
	p = n // 2
	for i in range(m):
		c.append(s[p])
		p += n // 2 + 1
	print(sum(c))


import math
t = int(input())
while t > 0:
	t -= 1
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	a.reverse()
	z = math.ceil(n / 2)
	i = n - z
	s = 0
	q = 0
	while i < n * k and q < k:
		s += a[i]
		q += 1
		i += n - z + 1
	print(s)


import math
t = int(input())
for _ in range(t):
	(a, b) = map(int, input().split())
	l = list(map(int, input().split()))
	ind = math.ceil(a / 2)
	x = 0
	ans = 0
	for i in range(1, b + 1):
		x = x + 1
		w = l[-(ind + (1 - math.ceil(a / 2) + math.floor(a / 2))) * x]
		ans = ans + w
	print(ans)


import sys
from collections import defaultdict as dc
from collections import Counter
from bisect import bisect_right, bisect_left
import math
from operator import itemgetter
from heapq import heapify, heappop, heappush
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	l = list(map(int, input().split()))
	x = math.ceil(n / 2)
	t = n - x
	s = 0
	c = 0
	a = 0
	t += 1
	for i in range(n * k - 1, -1, -1):
		c += 1
		if c % t == 0:
			s += l[i]
			a += 1
		if a == k:
			break
	print(s)


import os.path
import sys
from math import *
from math import floor, gcd, fabs, factorial, fmod, sqrt, inf, log
if os.path.exists('input.txt'):
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')

def inp():
	return sys.stdin.readline().strip()
for _ in range(int(inp())):
	(n, k) = map(int, inp().split())
	arr = list(map(int, inp().split()))
	ans = 0
	if n % 2 == 0:
		x = n // 2
	else:
		x = n // 2 + 1
	a = n - x + 1
	b = 0
	for i in range(len(arr) - a, -1, -a):
		if b == k:
			break
		ans += arr[i]
		b += 1
	print(ans)


import math

def maxMedian(nums, n, k):
	x = math.ceil(n / 2)
	medians = []
	flag = 0
	i = n * k - 1
	if n % 2 == 0:
		while len(medians) != k and i >= 0:
			flag += 1
			if flag == x + 1:
				medians.append(nums[i])
				flag = 0
			i -= 1
	else:
		while len(medians) != k and i >= 0:
			flag += 1
			if flag == x:
				medians.append(nums[i])
				flag = 0
			i -= 1
	return sum(medians)
t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	nums = list(map(int, input().split()))
	print(maxMedian(nums, n, k))


import math
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	li = list(map(int, input().split()))
	m = n // 2 + 1
	pos = n * k - m
	cnt = k
	res = 0
	while cnt > 0:
		res += li[pos]
		pos -= m
		cnt -= 1
	print(res)


for _ in range(int(input())):
	(n, k) = [int(i) for i in input().split()]
	lx = [int(i) for i in input().split()]
	l = 0
	r = n * k - 1
	ans = 0
	if n % 2 == 0:
		x = n // 2
	else:
		x = n // 2 + 1
	while l <= r:
		r -= n - x + 1
		l += x - 1
		ans += lx[r + 1]
	print(ans)


from sys import stdin, stdout
import math
import heapq
import collections
input = stdin.readline

def inputnum():
	return int(input())

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

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

def inputstring():
	return [x for x in input()]

def inputstrings():
	return [x for x in input().split()]

def inputstringnum():
	return [ord(x) - ord('a') for x in input()]

def inputmatrixchar(rows):
	arr2d = [[j for j in input().strip()] for i in range(rows)]
	return arr2d

def inputmatrixint(rows):
	arr2d = []
	for _ in range(rows):
		arr2d.append([int(i) for i in input().split()])
	return arr2d
t = int(input())
for q in range(t):
	(n, k) = inputnums()
	a = inputlist()
	x = n // 2 - (n % 2 == 0)
	sm = 0
	for i in range(x * k, n * k, n // 2 + 1):
		sm += a[i]
	print(sm)


import sys, math
input = sys.stdin.readline
t = int(input())
for r in range(t):
	(n, k) = map(int, input().split())
	l = list(map(int, input().split()))
	l.sort(reverse=True)
	step = math.ceil(n / 2)
	if n % 2 == 0:
		step += 1
	summ = 0
	start = n // 2
	count = 0
	while count < k:
		summ += l[start + step * count]
		count += 1
	print(summ)


import sys
input = sys.stdin.readline
t = int(input())
while t:
	(n, k) = map(int, input().split())
	l = list(map(int, input().split()))
	i = 0
	j = n * k
	if n % 2:
		ii = n // 2
		jj = n // 2 + 1
	else:
		ii = n // 2 - 1
		jj = n // 2 + 1
	su = 0
	while j - i >= 1:
		i = i + ii
		j = j - jj
		su += l[j]
	print(su)
	t -= 1


for _ in range(int(input())):
	(n, k) = input().split()
	(n, k) = (int(n), int(k))
	a = list(map(int, input().split()))
	a.sort()
	m = n // 2 + 1
	d = n * k
	sum = 0
	for i in range(0, k):
		sum += a[d - m]
		d -= m
	print(sum)


t = int(input())
for z in range(t):
	(n, k) = map(int, input().split())
	A = list(map(int, input().split()))
	m = n - (n // 2 + n % 2) + 1
	sum = 0
	for i in range(1, k + 1):
		sum += A[i * -m]
	print(sum)


t = int(input())
for i in range(t):
	v = [int(x) for x in input().split(' ')]
	a = [int(x) for x in input().split(' ')]
	n = v[0]
	k = v[1]
	d = 0
	ans = 0
	if n % 2 == 0:
		d = int(n / 2) + 1
	else:
		d = int((n + 1) / 2)
	l = d
	for i in range(k):
		ans += a[n * k - l]
		l = l + d
	print(ans)


def compute(ar, N, K, V):
	(c, ans, i) = (0, 0, N * K)
	while c != K:
		ans += ar[i - V]
		i -= V
		c += 1
	return ans
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	arr = list(map(int, input().split()))
	v = n // 2 + 1
	print(compute(arr, n, k, v))


t = int(input())
for time in range(t):
	(a, n) = map(int, input().split())
	l = list(map(int, input().split()))
	s = len(l)
	p = 0
	if a % 2 != 0:
		d = a // 2
		c = 0
		u = 0
		for i in range(s):
			if u == n:
				break
			if c == d:
				p = p + l[s - 1 - i]
				u = u + 1
				c = 0
			else:
				c = c + 1
	else:
		d = a // 2
		c = 0
		u = 0
		for i in range(s):
			if u == n:
				break
			if c == d - 1:
				p = p + l[s - 2 - i]
				c = -1
				u = u + 1
			else:
				c = c + 1
	print(p)


import sys, math
import io, os
from bisect import bisect_left as bl, bisect_right as br, insort
from heapq import heapify, heappush, heappop
from collections import defaultdict as dd, deque, Counter
from itertools import permutations, combinations

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

def mdata():
	return list(map(int, data().split()))

def outl(var):
	sys.stdout.write(' '.join(map(str, var)) + '\n')

def out(var):
	sys.stdout.write(str(var) + '\n')
sys.setrecursionlimit(100000)
INF = float('inf')
mod = int(1000000000.0) + 7
for t in range(int(data())):
	(n, k) = mdata()
	a = sorted(mdata())
	s = 0
	for i in range((n // 2 - 1 + n % 2) * k, n * k, n - n // 2 + 1 - n % 2):
		s += a[i]
	out(s)


import os
import sys
from io import BytesIO, IOBase
import math
import itertools as ITER
from collections import defaultdict as DIC
from collections import Counter as CO
from collections import deque as Q
import threading
from functools import lru_cache, reduce
from functools import cmp_to_key as CMP
from bisect import bisect_left as BL
from bisect import bisect_right as BR
import random as RA
import cmath, time
start_time = time.time()
MOD = 10 ** 9 + 7
MA = float('inf')
MI = float('-inf')

def increase_stack():
	sys.setrecursionlimit(2 ** 32 // 2 - 1)
	threading.stack_size(1 << 27)
	t = threading.Thread(target=main)
	t.start()
	t.join()

def prints(a):
	print(a, end='')

def binary(n):
	return bin(n)[2:]

def decimal(s):
	return int(s, 2)

def pow2(n):
	p = 0
	while n > 1:
		n //= 2
		p += 1
	return p

def factors(n):
	q = []
	for i in range(1, int(n ** 0.5) + 1):
		if n % i == 0:
			q.append(i)
			q.append(n // i)
	return list(sorted(list(set(q))))

def primeFactors(n):
	l = []
	while n % 2 == 0:
		l.append(2)
		n = n / 2
	for i in range(3, int(math.sqrt(n)) + 1, 2):
		while n % i == 0:
			l.append(i)
			n = n / i
	if n > 2:
		l.append(int(n))
	l.sort()
	return l

def isPrime(n):
	if n == 1:
		return False
	else:
		root = int(n ** 0.5)
		root += 1
		for i in range(2, root):
			if n % i == 0:
				return False
		return True

def seive(n):
	a = [1]
	prime = [True for i in range(n + 1)]
	p = 2
	while p * p <= n:
		if prime[p] == True:
			for i in range(p ** 2, n + 1, p):
				prime[i] = False
		p = p + 1
	for p in range(2, n + 1):
		if prime[p]:
			a.append(p)
	return a

def maxPrimeFactors(n):
	maxPrime = -1
	while n % 2 == 0:
		maxPrime = 2
		n >>= 1
	for i in range(3, int(math.sqrt(n)) + 1, 2):
		while n % i == 0:
			maxPrime = i
			n = n / i
	if n > 2:
		maxPrime = n
	return int(maxPrime)

def countchar(s, i):
	c = 0
	ch = s[i]
	for i in range(i, len(s)):
		if s[i] == ch:
			c += 1
		else:
			break
	return c

def str_counter(a):
	q = [0] * 26
	for i in range(len(a)):
		q[ord(a[i]) - 97] = q[ord(a[i]) - 97] + 1
	return q

def lis(arr):
	n = len(arr)
	lis = [1] * n
	maximum = 0
	for i in range(1, n):
		for j in range(0, i):
			if arr[i] > arr[j] and lis[i] < lis[j] + 1:
				lis[i] = lis[j] + 1
				maximum = max(maximum, lis[i])
	return maximum

def lcm(arr):
	a = arr[0]
	val = arr[0]
	for i in range(1, len(arr)):
		gcd = gcd(a, arr[i])
		a = arr[i]
		val *= arr[i]
	return val // gcd

def ncr(n, r):
	return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

def npr(n, r):
	return math.factorial(n) // math.factorial(n - r)

def inint():
	return int(input())

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

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

def instr():
	s = input()
	return list(s)
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
ONLINE = 1

def solve():
	(n, k) = invar()
	arr = inarr()
	if n == 1:
		print(sum(arr))
	elif n == 2:
		su = 0
		for i in range(0, len(arr), 2):
			su += arr[i]
		print(su)
	else:
		su = 0
		medind = math.ceil(n / 2) - 1
		lr = k * medind
		if lr == 0:
			lr = n - medind
		for i in range(lr, len(arr), n - medind):
			su += arr[i]
		print(su)

def main(flag):
	if not flag:
		sys.stdin = open('c:/Users/Manoj Chowdary/Documents/python/CodeForces/contest-div-2/input.txt', 'r')
		sys.stdout = open('c:/Users/Manoj Chowdary/Documents/python/CodeForces/contest-div-2/output.txt', 'w')
	t = inint()
	for _ in range(1, t + 1):
		solve()
	if not flag:
		print('Time: %.4f sec' % (time.time() - start_time))
		sys.stdout.close()
main(ONLINE)


import sys, math, itertools, collections, copy
input = sys.stdin.readline

def solve():
	(N, K) = map(int, input().split())
	arr = [int(x) for x in input().split()]
	size = len(arr)
	pos = 0
	if N & 1:
		pos = N // 2
	else:
		pos = N // 2 - 1
	after = N - pos - 1
	begin = size - after - 1
	step = -(after + 1)
	cnt = 0
	ans = 0
	for i in range(begin, -1, step):
		ans += arr[i]
		cnt += 1
		if cnt >= K:
			break
	print(ans)
for _ in range(int(input())):
	solve()


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	l = list(map(int, input().split()))
	if n % 2 == 0:
		a = n // 2 - 1
		b = (n - a) * -1
		s = 0
		ab = b
		for x in range(k):
			s += l[b]
			b += ab
		print(s)
	else:
		a = n // 2
		b = (n - a) * -1
		s = 0
		ab = b
		for x in range(k):
			s += l[b]
			b += ab
		print(s)


import sys
input = sys.stdin.buffer.readline

def solution():
	(n, k) = map(int, input().split())
	l = list(map(int, input().split()))
	l.sort()
	l = [0] + l
	i = 0
	j = n
	if n % 2 != 0:
		z = n + 1
		x = n // 2
		y = n // 2 + 1
	else:
		z = n
		y = n // 2 + 1
		x = n // 2 - 1
	a = x
	b = y
	ans = 0
	while k * n - b >= a:
		ans += l[len(l) - b]
		b += y
		a += x
	print(ans)
t = int(input())
for _ in range(t):
	solution()


from math import ceil
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	a = list(map(int, input().strip().split()))
	c = 0
	h = ceil(n / 2)
	i = n * k - (n - h) - 1
	while k > 0:
		c += a[i]
		i -= n - h + 1
		k -= 1
	print(c)


t = int(input())
for i in range(t):
	(n, k) = map(int, input().split())
	l = list(map(int, input().split()))
	c = n // 2 + 1
	ans = 0
	for j in range(c, c * k + 1, c):
		ans = ans + l[-j]
	print(ans)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	l = sorted(map(int, input().split()))
	ans = 0
	if n % 2 == 0:
		i = k * (n // 2 - 1)
		while i < n * k:
			ans += l[i]
			i += n - n // 2 + 1
		print(ans)
	else:
		i = k * (n // 2)
		while i < n * k:
			ans += l[i]
			i += n - n // 2
		print(ans)


import math
for t in range(int(input())):
	(n, k) = list(map(int, input().split()))
	li = list(map(int, input().split()))
	li.sort(reverse=True)
	sm = 0
	i = math.floor(n / 2)
	j = 0
	while j < k:
		sm += li[i]
		li = li[i + 1:]
		j += 1
	print(sm)


import math
ans = []
tests = int(input())
for i in range(tests):
	input_list = [int(x) for x in input().split(' ')]
	n = input_list[0]
	k = input_list[1]
	a = [int(x) for x in input().split(' ')]
	half = 0
	sum_of_medians = 0
	for j in range(k):
		half += math.floor(n / 2) + 1
		sum_of_medians += a[-half]
	ans.append(sum_of_medians)
for i in ans:
	print(i)


t = int(input())
for i in range(t):
	(n, k) = list(map(int, input().split()))
	a = list(map(int, input().split()))
	intv = n // 2 + 1
	mdn = a[-intv::-intv]
	print(sum(mdn[:k]))


import math
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	m = n * k
	a = list(map(int, input().split()))
	t = (n + 1) // 2 - 1
	t = n - t
	p = m - t
	cnt = 0
	ans = 0
	while cnt < k:
		ans += a[p]
		p -= t
		cnt += 1
	print(ans)


def C1():
	t = int(input())
	for _ in range(t):
		(n, k) = map(int, input().split())
		a = [int(i) for i in input().split()]
		mid = int(n / 2 + 1)
		ans = 0
		for i in range(k + 1):
			ind = n * k - i * mid
			if ind >= len(a):
				continue
			ans += a[ind]
		print(ans)
C1()


from sys import stdin, stdout
import math, sys, heapq
from itertools import permutations, combinations
from collections import defaultdict, deque, OrderedDict
from os import path
import random
import bisect as bi

def yes():
	print('YES')

def no():
	print('NO')
if path.exists('input.txt'):
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')

	def I():
		return int(input())

	def In():
		return map(int, input().split())
else:

	def I():
		return int(stdin.readline())

	def In():
		return map(int, stdin.readline().split())

def dict(a):
	d = {}
	for x in a:
		if d.get(x, -1) != -1:
			d[x] += 1
		else:
			d[x] = 1
	return d

def find_gt(a, x):
	i = bi.bisect_left(a, x)
	if i != len(a):
		return i
	else:
		return -1

def main():
	try:
		(n, k) = In()
		l = list(In())
		m = math.ceil(n / 2)
		s = n * k
		su = 0
		for i in range(k):
			s -= n - m + 1
			su += l[s]
		print(su)
	except:
		pass
M = 998244353
P = 1000000007
for _ in range(I()):
	main()


import math
for i in range(int(input())):
	(n, k) = map(int, input().split())
	l = [int(x) for x in input().split()]
	if n % 2 == 0:
		z = math.ceil(n / 2)
	else:
		z = n // 2
	sumval = 0
	lenv = len(l)
	for i in range(k):
		sumval += l[lenv - z - 1]
		lenv = lenv - z - 1
	print(sumval)


from math import *
t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	p = (n - 1) // 2
	q = n - p
	l = 0
	r = n * k
	ans = 0
	while l < r:
		r = r - q
		ans = ans + a[r]
		l = l + p
		if l >= r:
			break
	print(ans)


def main():
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	a.reverse()
	s = 0
	p = n // 2
	i = p
	for c in range(k):
		s += a[i]
		i += p + 1
	print(s)
rw = int(input())
for wewq in range(rw):
	main()


T = int(input())
for _ in range(0, T):
	(n, k) = map(int, input().split())
	s = [int(x) for x in input().split()]
	s = s[::-1]
	rr = n // 2
	r2 = rr + 1
	ans = 0
	for i in range(0, k):
		ans += s[rr]
		rr += r2
	print(ans)


def solve_Median(n, k, n_kArr):
	arr_size = n * k
	index1 = (n + 1) // 2 - 1
	index1 = n - index1
	s = arr_size + 1
	max_median = 0
	while k > 0:
		s -= index1
		if s <= 0:
			break
		max_median += n_kArr[s - 1]
		k -= 1
	return max_median
t = int(input())
temp_arr = []
for i in range(t):
	n_kList = list(map(int, input().split()))
	n = n_kList[0]
	k = n_kList[1]
	n_kArr = list(map(int, input().split()))
	max_median = solve_Median(n, k, n_kArr)
	temp_arr.append(max_median)
for j in temp_arr:
	print(j)


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

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

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

def invr():
	return map(int, input().split())
y = inp()
for _ in range(y):
	[n, k] = inlt()
	l = inlt()
	val = (n + 2) // 2
	lp = 0
	rp = n * k
	res = 0
	while lp < rp:
		rp -= val
		lp += n - val
		res += l[rp]
	print(res)


import math
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	l = list(map(int, input().split()))
	s = 0
	a = math.ceil(n / 2)
	for i in range(k * max(0, a - 1), n * k, n - a + 1):
		s += l[i]
	print(s)


import sys
from math import ceil
input = lambda : sys.stdin.readline()
int_arr = lambda : list(map(int, input().split()))
str_arr = lambda : list(map(str, input().split()))
get_str = lambda : map(str, input().split())
get_int = lambda : map(int, input().split())
get_flo = lambda : map(float, input().split())
mod = 1000000007

def solve(n, k, arr):
	if n % 2 != 0:
		n = ceil(n / 2)
	else:
		n = n // 2 + 1
	tot = 0
	c = 0
	for i in range(len(arr) - n, -1, -n):
		tot += arr[i]
		c += 1
		if c == k:
			print(tot)
			return
	print(tot)
for _ in range(int(input())):
	(n, k) = get_int()
	arr = int_arr()
	solve(n, k, arr)


from collections import Counter
from collections import OrderedDict
from collections import defaultdict
import bisect
import math
from sys import setrecursionlimit

def gcd(a, b):
	if a == 0:
		return b
	return gcd(b % a, a)

def fre_count(mylist):
	return Counter(mylist)
t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	arr = [int(x) for x in input().split()]
	step = n // 2 + 1
	sum1 = 0
	time = k
	for i in range(n * k - step, -1, step * -1):
		sum1 += arr[i]
		time -= 1
		if time <= 0:
			break
	print(sum1)


PI = 3.141592653589793
INF = 999999999
MOD = 1000000007
import random

def add(x, y):
	return (x + y) % MOD

def sub(x, y):
	return (x - y + MOD) % MOD

def mul(x, y):
	return x * y % MOD

def gcd(x, y):
	if y == 0:
		return x
	return gcd(y, x % y)

def lcm(x, y):
	return x * y // gcd(x, y)

def power(x, y):
	res = 1
	x %= MOD
	while y != 0:
		if y & 1:
			res = mul(res, x)
		y >>= 1
		x = mul(x, x)
	return res

def mod_inv(n):
	return power(n, MOD - 2)

def prob(p, q):
	return mul(p, power(q, MOD - 2))

def ii():
	return int(input())

def li():
	return [int(i) for i in input().split()]

def ls():
	return [i for i in input().split()]
for t in range(ii()):
	(n, k) = li()
	a = li()
	if n == 1:
		print(sum(a))
		continue
	ans = 0
	index = n // 2
	a.reverse()
	cnt = 0
	while index < n * k and cnt < k:
		ans += a[index]
		index += n // 2 + 1
		cnt += 1
	print(ans)


for _ in range(int(input())):
	(n, k) = (int(x) for x in input().split())
	a = list((int(x) for x in input().split()))
	s = 0
	if n % 2 == 0:
		b = n // 2
	else:
		b = n // 2 + 1
	j = n * k - 1 - n // 2
	for i in range(k):
		s += a[j]
		j = j - n // 2 - 1
	print(s)


from collections import defaultdict
linp = lambda : list(map(int, input().split()))
iinp = lambda : int(input())
tinp = lambda : map(int, input().split())
rinp = lambda : range(int(input()))
dct = lambda : defaultdict(lambda : 0)
from collections import Counter
from math import ceil
for _ in rinp():
	(n, k) = tinp()
	l = linp()
	i = ceil(n / 2)
	r = n - i + 1
	x = r
	sm = 0
	c = 0
	while c < k:
		sm += l[-x]
		x += r
		c += 1
	print(sm)


t = int(input())
for i in range(t):
	sum = 0
	j = 0
	(n, k) = [int(x) for x in input().split()]
	a = [int(s) for s in input().split()]
	while k != 0:
		j += 1 + n // 2
		sum += a[-j]
		k -= 1
	print(sum)


import sys
input = sys.stdin.readline
t = int(input())
for i in range(t):
	(n, k) = map(int, input().split())
	a = [int(i) for i in input().split() if i != '\n']
	a.sort()
	ans = []
	(diff, count) = (n - (n + 1) // 2, 0)
	for i in range(n * k - 1, -1, -1):
		if count == diff:
			ans.append(a[i])
			if len(ans) == k:
				break
			count = 0
		else:
			count += 1
	print(sum(ans))


inp = lambda : map(int, input().split(' '))
(t,) = inp()
for _ in range(t):
	(n, k) = inp()
	arr = list(inp())
	diff = n // 2
	index = n * k - 1
	sum = 0
	for i in range(k):
		sum += arr[index - diff]
		index = index - diff - 1
	print(sum)


import sys
import math
from collections import defaultdict as dd
mod = 1000000007
T = 1
T = int(sys.stdin.readline())
for _ in range(T):
	(n, k) = map(int, input().split())
	l = list(map(int, input().split()))
	ans = 0
	l = l[::-1]
	t = n // 2
	y = t
	while k:
		k -= 1
		ans += l[t]
		t += y + 1
	print(ans)


t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	b = [a[i] for i in range((n - 1) // 2 * k)]
	a = a[(n - 1) // 2 * k:]
	ip = 0
	ih = 0
	o = []
	ans = 0
	while ip < len(b) or ih < len(a):
		if len(o) < (n + 1) // 2 - 1 and ip < len(b):
			o.append(b[ip])
			ip += 1
		elif ih < len(a) and len(o) < n:
			o.append(a[ih])
			ih += 1
		elif len(o) < n:
			o.append(a[ip])
			ip += 1
		else:
			ans += o[(n - 1) // 2]
			o = []
	if len(o) > 0:
		ans += o[(n - 1) // 2]
	print(ans)


def maxMed(n, k, a):
	skips = n // 2
	i = len(a) - 1
	ans = 0
	while k:
		i = i - skips
		ans += a[i]
		i = i - 1
		k = k - 1
	return ans
t = int(input())
for i in range(t):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	print(maxMed(n, k, a))


t = int(input())
for _ in range(t):
	(n, k) = map(int, input().strip().split())
	arr = list(map(int, input().strip().split()))[:n * k]
	length_arr = n * k
	if n == 1:
		print(sum(arr))
		continue
	elif n == 2:
		tot = 0
		for i in range(0, length_arr, 2):
			tot += arr[i]
		print(tot)
		continue
	start = 0
	end = length_arr
	median_pos = n // 2
	low_val_pos = (n - 1) // 2
	high_val_pos = n - low_val_pos
	tot = 0
	while start < end:
		new_arr = arr[start:start + low_val_pos:1] + arr[end - high_val_pos:end:1]
		curr_median = new_arr[(n - 1) // 2]
		tot += curr_median
		start += low_val_pos
		end -= high_val_pos
	print(tot)


import math
T = int(input())
for t in range(T):
	(n, k) = map(int, input().split())
	A = list(map(int, input().split()))
	sum = 0
	med_numb = int(math.ceil(n / 2)) + (n + 1) % 2
	A.sort()
	point = n * k - med_numb
	for i in range(k):
		sum += A[point]
		point -= med_numb
	print(sum)


import math
for t in range(int(input())):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	s = 0
	if n % 2 == 1:
		d = math.ceil(n / 2)
		d = int(d)
		i = d - 1
		a.sort(reverse=True)
		while k > 0:
			k = k - 1
			s = s + a[i]
			i = i + d
	else:
		d = n // 2
		i = d
		a.sort(reverse=True)
		while k > 0:
			k = k - 1
			s = s + a[i]
			i = i + (d + 1)
	print(s)


import math
for z in range(int(input())):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	if n <= 2:
		i = 0
		l = 0
		while i <= k * n - 1:
			l += a[i]
			i += n
		print(l)
	else:
		d = math.ceil(n / 2) if n % 2 != 0 else math.ceil(n / 2) + 1
		i = k * (n - d)
		l = 0
		while i < n * k - 1:
			l += a[i]
			i += d
		print(l)


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

def i():
	return int(input())
for _ in range(i()):
	(n, k) = mp()
	l = list(mp())
	l.reverse()
	s = 0
	size = n // 2 + 1
	for i in range(k):
		s += l[n // 2 + i * size]
	print(s)


import sys
import math, bisect
sys.setrecursionlimit(10 ** 5)
from itertools import groupby, accumulate
from heapq import heapify, heappop, heappush
from collections import deque, Counter, defaultdict
I = lambda : int(sys.stdin.readline())
neo = lambda : map(int, sys.stdin.readline().split())
Neo = lambda : list(map(int, sys.stdin.readline().split()))
for _ in range(I()):
	(n, k) = neo()
	A = Neo()
	A.sort()
	A = A[::-1]
	t = n // 2 + n % 2
	Ans = 0
	q = n - t
	i = q
	while k:
		Ans += A[i]
		i += q + 1
		k -= 1
	print(Ans)


import math

def main():
	t = int(input())
	while t > 0:
		sumt = 0
		(n, k) = map(int, input().split())
		li = list(map(int, input().split()))
		cnt = 0
		mi = math.ceil(n // 2)
		for i in range(n * k - mi - 1, -1, -1 * (mi + 1)):
			if cnt < k:
				sumt = sumt + li[i]
				cnt = cnt + 1
		print(sumt)
		t -= 1
main()


import math
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	ans = 0
	p = math.ceil(n / 2)
	p -= 1
	start = p * k
	rem = n * k - p * k
	x = rem // k
	for i in range(start, n * k, x):
		ans += a[i]
	print(ans)


import sys
import os
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
mod = 10 ** 9 + 7

def lcm(x, y):
	return x * y / gcd(x, y)

def fact(x, mod=mod):
	ans = 1
	for i in range(1, x + 1):
		ans = ans * i % mod
	return ans

def arr2D(n, m, default=0):
	return [[default for j in range(m)] for i in range(n)]

def arr3D(n, m, r, default=0):
	return [[[default for k in range(r)] for j in range(m)] for i in range(n)]

def sortDictV(x):
	return {k: v for (k, v) in sorted(x.items(), key=lambda item: item[1])}

class DSU:

	def __init__(self, length):
		self.length = length
		self.parent = [-1] * self.length

	def getParent(self, node, start):
		if node >= self.length:
			return False
		if self.parent[node] < 0:
			if start != node:
				self.parent[start] = node
			return node
		return self.getParent(self.parent[node], start)

	def union(self, node1, node2):
		parent1 = self.getParent(node1, node1)
		parent2 = self.getParent(node2, node2)
		if parent1 == parent2:
			return False
		elif self.parent[parent1] <= self.parent[parent2]:
			self.parent[parent1] += self.parent[parent2]
			self.parent[parent2] = parent1
		else:
			self.parent[parent2] += self.parent[parent1]
			self.parent[parent1] = parent2
		return True

	def getCount(self, node):
		return -self.parent[self.getParent(node, node)]
from math import ceil

def solve(n, k, lst):
	lst = lst[::-1]
	summ = 0
	pos = n - ceil(n / 2)
	x = ceil(n / 2)
	if n % 2 == 0:
		x += 1
	ans = []
	for i in range(k):
		ans.append(lst[pos])
		summ += lst[pos]
		pos += x
	return summ
for _ in range(int(input())):
	(n, k) = list(map(int, input().split()))
	lst = list(map(int, input().split()))
	print(solve(n, k, lst))


from sys import stdin
from collections import Counter
from math import sqrt, factorial, log10, log, floor, ceil
from itertools import permutations, combinations, combinations_with_replacement
input = stdin.readline

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

def lis():
	return list(map(str, input().split()))

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

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

def inps():
	return str(input().strip())

def pr(n):
	return stdout.write(str(n) + '\n')
INF = float('inf')

def solve():
	(n, k) = mp()
	a = li()
	a.sort()
	r = n // 2
	x = n * k - r - 1
	sm = 0
	while k > 0:
		sm += a[x]
		x -= r + 1
		k -= 1
	print(sm)
t = inp()
for i in range(t):
	solve()


from __future__ import division, print_function
from fractions import Fraction
import sys
import os
from io import BytesIO, IOBase
from itertools import *
import bisect
from heapq import *
from math import ceil, floor
from copy import *
from collections import deque, defaultdict
from collections import Counter as counter
from itertools import combinations
from itertools import permutations as permutate
from bisect import bisect_left as bl
from operator import *
from bisect import bisect_right as br
from bisect import bisect
BUFSIZE = 8192
from sys import stderr

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')

def print(*args, **kwargs):
	(sep, file) = (kwargs.pop('sep', ' '), kwargs.pop('file', sys.stdout))
	at_start = True
	for x in args:
		if not at_start:
			file.write(sep)
		file.write(str(x))
		at_start = False
	file.write(kwargs.pop('end', '\n'))
	if kwargs.pop('flush', False):
		file.flush()
if sys.version_info[0] < 3:
	(sys.stdin, sys.stdout) = (FastIO(sys.stdin), FastIO(sys.stdout))
else:
	(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
from types import GeneratorType

def iterative(f, stack=[]):

	def wrapped_func(*args, **kwargs):
		if stack:
			return f(*args, **kwargs)
		to = f(*args, **kwargs)
		while True:
			if type(to) is GeneratorType:
				stack.append(to)
				to = next(to)
				continue
			stack.pop()
			if not stack:
				break
			to = stack[-1].send(to)
		return to
	return wrapped_func

class SortedList:

	def __init__(self, iterable=[], _load=200):
		values = sorted(iterable)
		self._len = _len = len(values)
		self._load = _load
		self._lists = _lists = [values[i:i + _load] for i in range(0, _len, _load)]
		self._list_lens = [len(_list) for _list in _lists]
		self._mins = [_list[0] for _list in _lists]
		self._fen_tree = []
		self._rebuild = True

	def _fen_build(self):
		self._fen_tree[:] = self._list_lens
		_fen_tree = self._fen_tree
		for i in range(len(_fen_tree)):
			if i | i + 1 < len(_fen_tree):
				_fen_tree[i | i + 1] += _fen_tree[i]
		self._rebuild = False

	def _fen_update(self, index, value):
		if not self._rebuild:
			_fen_tree = self._fen_tree
			while index < len(_fen_tree):
				_fen_tree[index] += value
				index |= index + 1

	def _fen_query(self, end):
		if self._rebuild:
			self._fen_build()
		_fen_tree = self._fen_tree
		x = 0
		while end:
			x += _fen_tree[end - 1]
			end &= end - 1
		return x

	def _fen_findkth(self, k):
		_list_lens = self._list_lens
		if k < _list_lens[0]:
			return (0, k)
		if k >= self._len - _list_lens[-1]:
			return (len(_list_lens) - 1, k + _list_lens[-1] - self._len)
		if self._rebuild:
			self._fen_build()
		_fen_tree = self._fen_tree
		idx = -1
		for d in reversed(range(len(_fen_tree).bit_length())):
			right_idx = idx + (1 << d)
			if right_idx < len(_fen_tree) and k >= _fen_tree[right_idx]:
				idx = right_idx
				k -= _fen_tree[idx]
		return (idx + 1, k)

	def _delete(self, pos, idx):
		_lists = self._lists
		_mins = self._mins
		_list_lens = self._list_lens
		self._len -= 1
		self._fen_update(pos, -1)
		del _lists[pos][idx]
		_list_lens[pos] -= 1
		if _list_lens[pos]:
			_mins[pos] = _lists[pos][0]
		else:
			del _lists[pos]
			del _list_lens[pos]
			del _mins[pos]
			self._rebuild = True

	def _loc_left(self, value):
		if not self._len:
			return (0, 0)
		_lists = self._lists
		_mins = self._mins
		(lo, pos) = (-1, len(_lists) - 1)
		while lo + 1 < pos:
			mi = lo + pos >> 1
			if value <= _mins[mi]:
				pos = mi
			else:
				lo = mi
		if pos and value <= _lists[pos - 1][-1]:
			pos -= 1
		_list = _lists[pos]
		(lo, idx) = (-1, len(_list))
		while lo + 1 < idx:
			mi = lo + idx >> 1
			if value <= _list[mi]:
				idx = mi
			else:
				lo = mi
		return (pos, idx)

	def _loc_right(self, value):
		if not self._len:
			return (0, 0)
		_lists = self._lists
		_mins = self._mins
		(pos, hi) = (0, len(_lists))
		while pos + 1 < hi:
			mi = pos + hi >> 1
			if value < _mins[mi]:
				hi = mi
			else:
				pos = mi
		_list = _lists[pos]
		(lo, idx) = (-1, len(_list))
		while lo + 1 < idx:
			mi = lo + idx >> 1
			if value < _list[mi]:
				idx = mi
			else:
				lo = mi
		return (pos, idx)

	def add(self, value):
		_load = self._load
		_lists = self._lists
		_mins = self._mins
		_list_lens = self._list_lens
		self._len += 1
		if _lists:
			(pos, idx) = self._loc_right(value)
			self._fen_update(pos, 1)
			_list = _lists[pos]
			_list.insert(idx, value)
			_list_lens[pos] += 1
			_mins[pos] = _list[0]
			if _load + _load < len(_list):
				_lists.insert(pos + 1, _list[_load:])
				_list_lens.insert(pos + 1, len(_list) - _load)
				_mins.insert(pos + 1, _list[_load])
				_list_lens[pos] = _load
				del _list[_load:]
				self._rebuild = True
		else:
			_lists.append([value])
			_mins.append(value)
			_list_lens.append(1)
			self._rebuild = True

	def discard(self, value):
		_lists = self._lists
		if _lists:
			(pos, idx) = self._loc_right(value)
			if idx and _lists[pos][idx - 1] == value:
				self._delete(pos, idx - 1)

	def remove(self, value):
		_len = self._len
		self.discard(value)
		if _len == self._len:
			raise ValueError('{0!r} not in list'.format(value))

	def pop(self, index=-1):
		(pos, idx) = self._fen_findkth(self._len + index if index < 0 else index)
		value = self._lists[pos][idx]
		self._delete(pos, idx)
		return value

	def bisect_left(self, value):
		(pos, idx) = self._loc_left(value)
		return self._fen_query(pos) + idx

	def bisect_right(self, value):
		(pos, idx) = self._loc_right(value)
		return self._fen_query(pos) + idx

	def count(self, value):
		return self.bisect_right(value) - self.bisect_left(value)

	def __len__(self):
		return self._len

	def __getitem__(self, index):
		(pos, idx) = self._fen_findkth(self._len + index if index < 0 else index)
		return self._lists[pos][idx]

	def __delitem__(self, index):
		(pos, idx) = self._fen_findkth(self._len + index if index < 0 else index)
		self._delete(pos, idx)

	def __contains__(self, value):
		_lists = self._lists
		if _lists:
			(pos, idx) = self._loc_left(value)
			return idx < len(_lists[pos]) and _lists[pos][idx] == value
		return False

	def __iter__(self):
		return (value for _list in self._lists for value in _list)

	def __reversed__(self):
		return (value for _list in reversed(self._lists) for value in reversed(_list))

	def __repr__(self):
		return 'SortedList({0})'.format(list(self))
mod = 1000000007

def inp():
	return sys.stdin.readline().rstrip('\r\n')

def out(var):
	sys.stdout.write(str(var))

def lis():
	return list(map(int, inp().split()))

def stringlis():
	return list(map(str, inp().split()))

def sep():
	return map(int, inp().split())

def strsep():
	return map(str, inp().split())

def fsep():
	return map(float, inp().split())

def nextline():
	out('\n')

def testcase(t):
	for p in range(t):
		solve()

def pow(x, y, p):
	res = 1
	x = x % p
	if x == 0:
		return 0
	while y > 0:
		if y & 1 == 1:
			res = res * x % p
		y = y >> 1
		x = x * x % p
	return res
from functools import reduce

def factors(n):
	return set(reduce(list.__add__, ([i, n // i] for i in range(1, int(n ** 0.5) + 1) if n % i == 0)))

def gcd(a, b):
	if a == b:
		return a
	while b > 0:
		(a, b) = (b, a % b)
	return a

def prefix_sum(ar):
	return list(accumulate(ar))

def suffix_sum(ar):
	return list(accumulate(ar[::-1]))[::-1]

def N():
	return int(inp())
dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]

def YES():
	print('YES')

def NO():
	print('NO')

def Yes():
	print('Yes')

def No():
	print('No')
from collections import defaultdict

def numberOfSetBits(i):
	i = i - (i >> 1 & 1431655765)
	i = (i & 858993459) + (i >> 2 & 858993459)
	return ((i + (i >> 4) & 252645135) * 16843009 & 4294967295) >> 24

def lcm(a, b):
	return abs(a // gcd(a, b) * b)

def nc2(n):
	return n * (n - 1) // 2

def solve():
	(n, k) = sep()
	ar = lis()[::-1]
	req = n - (n + 1) // 2
	s = 0
	ch = 0
	for i in range(req, len(ar), req + 1):
		s += ar[i]
		ch += 1
		if ch >= k:
			break
	print(s)
testcase(int(inp()))


n = int(input())
while n:
	list1 = list(map(int, input().split()))
	list2 = list(map(int, input().split()))
	k = list1[0] // 2
	j = 0
	num = 0
	for i in range(list1[0] * list1[1] - k - 1, -1, -(k + 1)):
		num += list2[i]
		j += 1
		if j == list1[1]:
			break
	print(num)
	n -= 1


t = int(input())
while t:
	(size, cntOfSubArr) = map(int, input().split(' '))
	arr = list(map(int, input().split(' ')))
	noOfElementsBeforeMedian = size // 2 if size % 2 else size // 2 - 1
	noOfElementsAfterMedian = size // 2
	N = size * cntOfSubArr
	ans = 0
	for indxOfMedian in range(noOfElementsBeforeMedian * cntOfSubArr, N, noOfElementsAfterMedian + 1):
		ans += arr[indxOfMedian]
	print(ans)
	t -= 1


from math import ceil
t = int(input())
for _ in range(t):
	(n, k) = tuple(map(int, input().split()))
	l = list(map(int, input().split()))
	x = ceil(n / 2) - 1
	sum = 0
	for i in range(x * k, len(l), n - x):
		sum += l[i]
	print(sum)


t = int(input())
for i in range(t):
	(n, k) = [int(x) for x in input().split()]
	a = [int(x) for x in input().split()]
	res = 0
	if n == 1:
		res = sum(a)
	elif n == 2:
		for i in range(0, n * k, 2):
			res += a[i]
	else:
		check = 0
		for i in range(n * k - n // 2 - 1, -1, -((n + 2) // 2)):
			check += 1
			res += a[i]
			if check == k:
				break
	print(res)


t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	if n % 2 == 0:
		x = n // 2
	else:
		x = n // 2 + 1
	c = 0
	i = n * k - (n - x) - 1
	y = n * k - i
	sum = 0
	while c < k:
		sum += a[i]
		i -= y
		c += 1
	print(sum)


import sys
from collections import defaultdict as dd
from collections import Counter as cc
from queue import Queue
import math
import itertools
try:
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')
except:
	pass
input = lambda : sys.stdin.readline().rstrip()
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	q = sorted(list(map(int, input().split())))
	w = n - (n + 1) // 2 + 1
	e = 0
	r = 0
	for i in range(n * k - w, -1, -w):
		r += 1
		e += q[i]
		if r == k:
			break
	print(e)


for i in range(int(input())):
	w = input().split(' ')
	arr = input().split(' ')
	n = int(w[0])
	k = int(w[1])
	ind = 0
	if n // 2 == n / 2:
		ind = int(n / 2)
	else:
		ind = int(n / 2 + 1)
	med = 0
	tlb = n - ind
	p = len(arr) - 1 - tlb
	for i in range(k):
		ele = int(arr[p])
		med = med + ele
		p = p - tlb - 1
	print(med)


import math
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	l = list(map(int, input().split()))
	ans = 0
	if n % 2 == 0:
		s = n // 2
		t = s + 1
		s = s + 1
		n = n * k
		for i in range(k):
			ans += l[n - s]
			s = s + t
	else:
		s = math.ceil(n / 2)
		n = n * k
		t = s
		for i in range(k):
			ans += l[n - s]
			s = s + t
	print(ans)


for etstcase in range(int(input())):
	arr = [int(x) for x in input().split()]
	(n, k) = (arr[0], arr[1])
	arr = [int(x) for x in input().split()]
	if n % 2 == 1:
		med = (n + 1) // 2
	else:
		med = n // 2
	big = n - med + 1
	sm = n - big
	j = n * k - big
	i = sm - 1
	ans = 0
	while i < j:
		ans += arr[j]
		j -= big
		i += sm
	print(ans)


for p in range(int(input())):
	(n, k) = list(map(int, input().split()))
	a = list(map(int, input().split()))
	if n % 2:
		(x, y) = (n // 2, n // 2 + 1)
	else:
		(x, y) = (n // 2 - 1, n // 2 + 1)
	if n == 2:
		s = 0
		for i in range(0, n * k, 2):
			s += a[i]
		print(s)
	else:
		(d, s) = (x * k, 0)
		while d < n * k:
			s += a[d]
			d += y
		print(s)


import math
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	l = list(map(int, input().split()))
	median = math.ceil(n / 2) - 1
	pos = 0
	index = 0
	i = 0
	ans = 0
	j = len(l) - 1
	while index < k:
		try:
			ans += l[j - (n - 1 - median)]
			j = j - (n - 1 - median) - 1
			index += 1
		except:
			index += 1
	print(ans)


import os
import sys
from io import BytesIO, IOBase

def main():
	for t in range(int(input())):
		(n, k) = map(int, input().split())
		a = list(map(int, input().split()))
		step = n - (n + 1) // 2
		s = 0
		c = 0
		for i in range(len(a) - 1 - step, -1, -step - 1):
			s += a[i]
			c += 1
			if c == k:
				break
		print(s)
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
main()


import math
test = int(input())
for t in range(test):
	(n, k) = map(int, input().split())
	l = list(map(int, input().split()))
	if n == 1:
		print(sum(l))
	else:
		ans = None
		cal = int(math.ceil(n / 2))
		count = 1
		ans_1 = 0
		while count <= k:
			ans_1 += l[cal * count - 1]
			count += 1
		if n == 2:
			median = 2
		elif n % 2 == 0:
			median = n // 2 + 1
		else:
			median = int(math.ceil(n / 2))
		ans = 0
		count = 1
		while count <= k:
			ans += l[-(median * count)]
			count += 1
		print(max(ans, ans_1))


from __future__ import division, print_function
from fractions import Fraction
import sys
import os
from io import BytesIO, IOBase
from functools import cmp_to_key
from heapq import *
from math import gcd, factorial, floor, ceil, sqrt
from copy import deepcopy
from collections import deque
from bisect import bisect_left as bl
from bisect import bisect_right as br
from bisect import bisect
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')

def print(*args, **kwargs):
	(sep, file) = (kwargs.pop('sep', ' '), kwargs.pop('file', sys.stdout))
	at_start = True
	for x in args:
		if not at_start:
			file.write(sep)
		file.write(str(x))
		at_start = False
	file.write(kwargs.pop('end', '\n'))
	if kwargs.pop('flush', False):
		file.flush()
if sys.version_info[0] < 3:
	(sys.stdin, sys.stdout) = (FastIO(sys.stdin), FastIO(sys.stdout))
else:
	(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
from types import GeneratorType

def iterative(f, stack=[]):

	def wrapped_func(*args, **kwargs):
		if stack:
			return f(*args, **kwargs)
		to = f(*args, **kwargs)
		while True:
			if type(to) is GeneratorType:
				stack.append(to)
				to = next(to)
				continue
			stack.pop()
			if not stack:
				break
			to = stack[-1].send(to)
		return to
	return wrapped_func

def inp():
	return sys.stdin.readline().rstrip('\r\n')

def out(var):
	sys.stdout.write(str(var))

def lis():
	return list(map(int, inp().split()))

def stringlis():
	return list(map(str, inp().split()))

def sep():
	return map(int, inp().split())

def strsep():
	return map(str, inp().split())

def testcase(t):
	for pp in range(t):
		solve(pp)

def google(p):
	print('Case #' + str(p) + ': ', end='')

def lcm(a, b):
	return a * b // gcd(a, b)

def power(x, y, p):
	y %= p - 1
	res = 1
	x = x % p
	if x == 0:
		return 0
	while y > 0:
		if y & 1 == 1:
			res = res * x % p
		y = y >> 1
		x = x * x % p
	return res

def ncr(n, r):
	return factorial(n) // (factorial(r) * factorial(max(n - r, 1)))

def isPrime(n):
	if n <= 1:
		return False
	if n <= 3:
		return True
	if n % 2 == 0 or n % 3 == 0:
		return False
	i = 5
	while i * i <= n:
		if n % i == 0 or n % (i + 2) == 0:
			return False
		i = i + 6
	return True
inf = pow(10, 20)
mod = 10 ** 9 + 7

def solve(case):
	(n, k) = sep()
	a = lis()
	a = sorted(a)
	g = [[] for i in range(k)]
	for i in range(k):
		for j in range(n):
			g[i].append(a[n * i + j])
	ans = 0
	ind = n * k - n // 2
	while ind > k * ((n - 1) // 2):
		ans += a[ind - 1]
		ind -= n // 2 + 1
	print(ans)
testcase(int(inp()))


from sys import *
from collections import defaultdict as dd
from math import *
from bisect import *

def sinp():
	return input()

def inp():
	return int(sinp())

def minp():
	return map(int, sinp().split())

def linp():
	return list(minp())

def strl():
	return list(sinp())

def pr(x):
	print(x)
mod = int(1000000000.0 + 7)
for _ in range(inp()):
	(n, k) = minp()
	a = linp()
	a.sort()
	m = (n + 1) // 2 - 1
	s = 0
	if m == 0:
		for i in range(0, n * k, n):
			s += a[i + m]
	else:
		c = 0
		m = n - m
		for i in range(n * k - m, -1, -m):
			s += a[i]
			c += 1
			if c == k:
				break
	pr(s)


t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	l1 = list(map(int, input().split()))
	l1.insert(0, 0)
	ans = 0
	if n == 2:
		for i in range(1, n * k + 1, 2):
			ans += l1[i]
		print(ans)
	else:
		if n % 2 == 0:
			x = n // 2
		else:
			x = n // 2 + 1
		a = x - 1
		b = n - x + 1
		i = a
		j = n * k + 1 - b
		while i < j:
			ans += l1[j]
			i += a
			j -= b
		print(ans)


for _ in range(int(input())):
	(n, k) = list(map(int, input().split()))
	lis = list(map(int, input().split()))
	x = n - (n - 1) // 2
	z = n * k - x
	y = lis[z]
	for i in range(k - 1):
		z -= x
		y += lis[z]
	print(y)


def solve(n, k, ass):
	kk = n // 2 + 1
	ans = 0
	ind = n * k - kk
	for _ in range(k):
		ans += ass[ind]
		ind -= kk
	return ans
for _ in range(int(input())):
	(n, k) = [int(x) for x in input().split()]
	ass = [int(x) for x in input().split()]
	print(solve(n, k, ass))


import math
test = int(input())
for t in range(test):
	nk = [int(num) for num in input().split()]
	n = nk[0]
	k = nk[1]
	l = [int(num) for num in input().split()]
	med = math.ceil(n / 2)
	summ = 0
	for i in range(k):
		summ += l[k * (med - 1) + i * (n - med + 1)]
	print(summ)


q = int(input())
for _ in range(q):
	(n, k) = map(int, input().split())
	alist = [*map(int, input().split())]
	numbers = n // 2 + 1
	asum = 0
	for i in range(n * k)[-numbers:-numbers * k - 1:-numbers]:
		asum += alist[i]
	print(asum)


import math
t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	arr = list(map(int, input().split()))
	cnt = 0
	steping = -(n - math.ceil(n / 2) + 1)
	b = steping
	for i in range(k):
		cnt += arr[steping]
		steping += b
	print(cnt)


import math
for t in range(int(input())):
	(n, k) = map(int, input().split())
	l1 = list(map(int, input().split()))
	m = math.ceil(n / 2)
	st = (m - 1) * k
	gap = n - m + 1
	su = 0
	for i in range(st, n * k, gap):
		su += l1[i]
	print(su)


from math import *
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	size = n * k
	l = [*map(int, input().split())]
	ans = [[] for i in range(k)]
	i = 0
	j = 0
	while j < n:
		j += 1
		x = i + k
		ind = 0
		if j >= int(ceil(n / 2)):
			y = n - len(ans[0])
			for m in range(k):
				ans[m].extend(l[i:i + y])
				i += y
			break
		while i < x:
			ans[ind].append(l[i])
			ind += 1
			i += 1
	result = 0
	if n % 2 == 0:
		for i in range(k):
			result += ans[i][n // 2 - 1]
	else:
		for i in range(k):
			result += ans[i][n // 2]
	print(result)


import collections
import math
import sys
input = sys.stdin.readline
t = int(input())
for i in range(t):
	s = input().split(' ')
	n = int(s[0])
	k = int(s[1])
	arr = collections.deque([])
	ss = input().replace('\n', '').replace('\r', '').split(' ')
	for sss in ss:
		arr.append(int(sss))
	median_idx = int(math.ceil(n / 2)) - 1
	ans = []
	for j in range(k):
		tmp = []
		for l in range(median_idx):
			tmp.append(arr.popleft())
		tmp.append(arr.pop())
		for l in range(n - median_idx - 1):
			tmp.append(arr.pop())
		tmp.sort()
		ans.append(tmp)
	ans_sum = 0
	for j in range(k):
		ans_sum += ans[j][median_idx]
	print(ans_sum)


n = int(input())
for i in range(n):
	(a, b) = map(int, input().split())
	l = list(map(int, input().split()))
	t = b
	ind = len(l) - a // 2 - 1
	s = 0
	while t > 0:
		s += l[ind]
		ind = ind - a // 2 - 1
		t -= 1
	print(s)


t = int(input())
while t:
	t -= 1
	(n, k) = map(int, input().split())
	nk = list(map(int, input().split()))
	median = 0
	for i in range(k):
		nk = nk[:len(nk) - n // 2]
		median += nk[-1]
		nk.pop()
	print(median)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	arr = list(map(int, input().split()))
	big = int(n / 2)
	pos = n * k - 1
	count = 0
	for i in range(k):
		for j in range(big):
			pos -= 1
		count += arr[pos]
		pos -= 1
	print(count)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	d = n // 2
	s = 0
	i = n * k
	for _ in range(k):
		s += a[i - d - 1]
		i -= d + 1
	print(s)


n_test = int(input())
for i in range(n_test):
	(n, k) = list(map(int, input().split()))
	arr = [int(m) for m in input().split(' ')]
	if n % 2 == 0:
		a = n // 2
	else:
		a = n // 2 + 1
	sum = 0
	b = 1
	for j in range(k):
		sum += arr[-b * (n - a) - b]
		b = b + 1
	print(sum)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	l = sorted(list(map(int, input().split())), reverse=True)
	res = 0
	t = 0
	if n > 1:
		t = n // 2
	if n == 2:
		for i in range(t, len(l), n):
			res += l[i]
	else:
		x = 0
		for i in range(t, len(l), t + 1):
			res += l[i]
			x += 1
			if x == k:
				break
	print(res)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	l = list(map(int, input().split()))
	p = list()
	if n % 2 == 0:
		m = n // 2
	else:
		m = n // 2 + 1
	w = n - m + 1
	for i in range(k * (m - 1), len(l) - w + 1, w):
		ans = l[i]
		p.append(ans)
	print(sum(p))


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	a = a[::-1]
	s = 0
	t = 0
	for i in range(n // 2, len(a), n // 2 + 1):
		s += a[i]
		t += 1
		if t == k:
			break
	print(s)


def solve():
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	q = n // 2 + 1
	print(sum(a[-q::-q][:k]))
for _ in range(int(input())):
	solve()


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	s = 0
	e = n * k
	ans = 0
	for i in range(k):
		if n % 2 == 0:
			y = n // 2 + 1
			z = n - y
			x = a[s:s + z] + a[e - y:e]
			ans += x[n // 2 - 1]
			s = s + z
			e = e - y
		else:
			y = n // 2
			z = n - y
			x = a[s:s + y] + a[e - z:e]
			ans += x[n // 2]
			s = s + y
			e = e - z
	print(ans)


t = int(input())
for p in range(t):
	(len_of_ans_block, number_of_ans_blocks) = map(int, input().split())
	array = list(map(int, input().split()))
	if len_of_ans_block == 1:
		print(sum(array))
	else:
		array = array[(len_of_ans_block - 1) // 2 * number_of_ans_blocks:len(array) - 1]
		ans = 0
		for i in range(len(array)):
			if i % (len_of_ans_block - (len_of_ans_block - 1) // 2) == 0:
				ans += array[i]
		print(ans)


def solve(lst, n, k):
	sm = 0
	cnt = 0
	x = n // 2
	i = n * k - 1 - x
	while i >= 0:
		if cnt == k:
			return sm
		sm += lst[i]
		i = i - x - 1
		cnt += 1
	return sm
t = int(input())
for i in range(t):
	(n, k) = map(int, input().split(' '))
	lst = list(map(int, input().split(' ')))
	print(solve(lst, n, k))


class Solution:

	def median(self, n, k, arr) -> int:
		arr = arr[::-1]
		ans = 0
		start = n // 2
		val = start + 1
		jump = 1
		while jump <= k:
			ans += arr[start]
			jump += 1
			start = start + val
		return ans
t = int(input())
for _ in range(t):
	(n, k) = list(map(int, input().split()))
	arr = list(map(int, input().split()))
	obj = Solution()
	print(obj.median(n, k, arr))


cases = int(input())
while cases:
	cases -= 1
	(a, b) = map(int, input().split())
	arr = list(map(int, input().split()))
	ln = a * b
	cut = (a - 1) // 2 * b
	a -= (a - 1) // 2
	arr = arr[cut:]
	ans = 0
	for i in range(0, ln - cut, a):
		ans += arr[i]
	print(ans)


import math
t = int(input())
for i in range(t):
	y = [int(i) for i in input().split()]
	n = y[0]
	k = y[1]
	y = [int(i) for i in input().split()]
	y.reverse()
	y.sort()
	s = 0
	for j in range(1, k + 1):
		s += y[n * k - j * (n // 2 + 1)]
	print(s)


testCases = int(input())
answer = []
for i in range(testCases):
	input1 = list(map(int, input().split(' ')))
	input2 = list(map(int, input().split(' ')))
	n = input1[0]
	k = input1[1]
	offset = (n + 1) // 2 - 1
	offset = n - offset
	calcIndex = k * n + 1
	ans = 0
	while k != 0:
		calcIndex -= offset
		if calcIndex <= 0:
			break
		ans += input2[calcIndex - 1]
		k -= 1
	answer.append(ans)
for i in answer:
	print(i)


t = int(input())
for i10 in range(t):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	a.sort()
	c = n // 2 + 1
	s = 0
	j = 1
	k1 = 0
	for i in range(n * k - 1, -1, -1):
		if k1 == k:
			break
		if j == c:
			k1 += 1
			j = 1
			s += a[i]
		else:
			j += 1
	print(s)


inn = lambda : int(input())
inm = lambda : map(int, input().split())
ins = lambda : str(input())
ina = lambda : list(map(int, input().split()))

def solve():
	(n, k) = inm()
	m = n * k
	a = ina()
	t = (n + 1) // 2 - 1
	t = n - t
	p = m - t
	cnt = 0
	ans = 0
	while cnt < k:
		ans += a[p]
		p -= t
		cnt += 1
	print(ans)

def main():
	t = 1
	t = int(input())
	for _ in range(t):
		solve()
main()


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	arr = list(map(int, input().split()))
	arr.sort(reverse=True)
	sum1 = 0
	l = n // 2
	for i in range(k):
		sum1 += arr[l]
		l += n // 2 + 1
	print(sum1)


import bisect
import math

def solve(n, k, arr):
	arr = arr[::-1]
	med = n - math.ceil(n / 2)
	Sum = 0
	ks = 0
	for z in range(med, k * n, med + 1):
		ks += 1
		Sum += arr[z]
		if k == ks:
			break
	return Sum
t = int(input())
ans = []
for i in range(t):
	nk = [int(x) for x in input().split()]
	n = nk[0]
	k = nk[1]
	arr = [int(x) for x in input().split()]
	ans.append(solve(n, k, arr))
for test in ans:
	print(test)


for t in range(int(input())):
	(n, k) = map(int, input().split())
	l = list(map(int, input().split()))
	if n == 1:
		print(sum(l))
	elif n == 2:
		print(sum(l[::2]))
	elif n % 2 == 0:
		s = 0
		for i in range(1, k + 1):
			s = s + l[-(i * (n // 2 + 1))]
		print(s)
	else:
		s = 0
		for i in range(1, k + 1):
			s = s + l[-(i * (n // 2 + 1))]
		print(s)


import sys
t = int(input())
for i in range(t):
	(n, k) = map(int, sys.stdin.readline().split())
	m = [int(x) for x in sys.stdin.readline().split()]
	mx = 0
	lt = int(n / 2) + 1
	for h in range(k):
		for j in range(lt - 1):
			m.pop()
		mx += m.pop()
	print(mx)


def medsum(n, k, arr):
	arr.sort()
	return sum(arr[(n - 1) // 2 * k:n * k:n // 2 + 1])
t = int(input())
for i in range(t):
	(n, k) = map(int, input().split())
	arr = list(map(int, input().split()))
	print(medsum(n, k, arr))


pas = lambda x: x // 2 + 1
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	print(sum(list(map(int, input().split()))[-pas(n)::-pas(n)][:k]))


def ceil(a, b):
	return (a + b - 1) // b

def main(a, k, n):
	med = ceil(n, 2)
	i = n * k - (n - med + 1)
	step = 0
	s = 0
	while step < k:
		s += a[i]
		i -= n - med + 1
		step += 1
	print(s)
	return ''
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	main(a, k, n)


from sys import stdin, stdout

def II():
	return int(stdin.readline())

def MI():
	return map(int, stdin.readline().split())

def LI():
	return list(map(int, stdin.readline().split()))

def solve():
	(n, k) = MI()
	a = LI()
	if n % 2 == 1:
		pl = (n - 1) // 2
		sl = pl
	else:
		pl = (n - 2) // 2
		sl = n // 2
	s = pl * k
	nk = n * k
	ans = sum([a[i] for i in range(s, nk, sl + 1)])
	stdout.write('{} \n'.format(ans))
t = II()
for _ in range(t):
	solve()


t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	nums = list(map(int, input().split()))
	total = n * k
	ans = 0
	if n == 1:
		ans = sum(nums)
	elif n == 2:
		for i in range(k):
			ans += nums[i * 2]
	elif n % 2 == 1:
		for i in range(n // 2 * k, total, n // 2 + 1):
			ans += nums[i]
	elif n % 2 == 0:
		for i in range((n // 2 - 1) * k, total, n - (n // 2 - 1)):
			ans += nums[i]
	print(ans)


import sys

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

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

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

def get_int():
	return int(sys.stdin.readline().strip())

def get_print_int(x):
	sys.stdout.write(str(x) + '\n')

def get_print(x):
	sys.stdout.write(x + '\n')
from math import ceil

def solve():
	for _ in range(get_int()):
		(n, k) = get_ints()
		arr = get_list()
		arr.sort()
		ans = 0
		(i, j) = (0, n * k - 1)
		mid = ceil(n / 2)
		while i <= j:
			temp = j - (n - 1)
			x = [arr[i]] + arr[temp + 1:j + 1]
			ans += x[mid - 1]
			i += 1
			j = temp
		anst = 0
		(i, j) = (0, n - 1)
		while j < n * k:
			anst += arr[i + (mid - 1)]
			i = j + 1
			j += n
		anstt = 0
		i = k * (mid - 1)
		while i < n * k:
			anstt += arr[i]
			i += n - mid + 1
		get_print_int(max(ans, anst, anstt))
solve()


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	a = [int(i) for i in input().split()]
	x = n // 2 + 1
	ans = 0
	t = 0
	for i in range(n * k - x, -1, -x):
		if t == k:
			break
		t += 1
		ans += a[i]
	print(ans)


from math import ceil

def fun(ls, n, k):
	median_position = ceil(n / 2)
	median_index = median_position - 1
	waste_elements = n - median_position
	ans = 0
	count = 0
	number_of_mediums = 0
	for i in ls[-1::-1]:
		count += 1
		if number_of_mediums >= k:
			break
		if count > waste_elements:
			ans += i
			count = 0
			number_of_mediums += 1
	print(ans)
T = int(input())
for i in range(T):
	(n, k) = list(map(int, input().split()))
	ls = list(map(int, input().split()))
	fun(ls, n, k)


from math import ceil
for testcase in range(int(input())):
	(n, k) = list(map(int, input().split()))
	values = list(map(int, input().split()))
	median_index = ceil(n / 2)
	elements_before_median = median_index - 1
	print(sum(values[elements_before_median * k::n - elements_before_median]))


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	lst = [int(x) for x in input().split()]
	lst.sort(reverse=True)
	temp = []
	w = n // 2
	for i in range(k):
		temp.append(lst[w])
		w += n // 2 + 1
	print(sum(temp))


for _ in range(int(input())):
	(N, k) = map(int, input().split())
	arr = list(map(int, input().split()))
	arr.insert(0, 0)
	n = (N + 1) // 2
	res = 0
	for i in range((n - 1) * k + 1, N * k + 1, N - n + 1):
		res += arr[i]
	print(res)