Read problem statements in [Bengali], [Mandarin Chinese], [Russian], and [Vietnamese] as well.

It’s Chef's birthday. He and his twin have received $N$ gifts in total. The $i$-th gift has a price of $A_{i}$. Each twin wants to keep the most expensive gifts for himself. 

The twins take $K$ turns alternately (each has $K$ turns, for $2\cdot K$ turns in total). It is given that $2\cdot K+1 ≤ N$. In a turn, a person may choose one gift. The only exception is the last turn of the twin who moves second, where he gets to choose two gifts instead of one. Assuming they both choose gifts optimally and you can choose who takes the first turn, find the maximum total cost of the gifts that Chef keeps. 

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

The first line contains an integer $T$, the number of test cases. Then the test cases follow. 
Each test case contains two lines of input.
The first line contains two space-separated integers $N$, $K$.
The second line contains $N$ space-separated integers $A_{1}, A_{2}, \ldots, A_{N}$, the price of the gifts.

------ Output ------
For each test case, output in a single line the answer to the problem.

------ Constraints  ------
$1 ≤ T ≤ 100$
$3 ≤ N ≤ 10^{3}$
$1 ≤ K ≤ \frac{N - 1}{2}$
$1 ≤ A_{i} ≤ 10^{9}$

------ Subtasks ------
Subtask #1 (100 points): original constraints

----- Sample Input 1 ------ 
3

3 1

1 3 2

3 1

3 1 3

5 2

5 1 3 2 4
----- Sample Output 1 ------ 
3

4

8
----- explanation 1 ------ 
Test Case $1$: Chef moves first and he chooses the gift with cost $3$. His twin then chooses the gifts of costs $1$ and $2$.

Test Case $2$: Chef allows his brother to choose first and his brother chooses a gift with cost $3$. Then Chef chooses the remaining gift with cost $3$. Since Chef moves second, he is allowed to choose one more gift, so he chooses gift with cost $1$. The total cost of Chef's gifts is $3 + 1 = 4$.

Test Case $3$: Chef moves first and at the end he will have the gifts with costs $5$ and $3$. Hence, the total cost of gifts with Chef = $5 + 3 = 8$.

Difficulty: MEDIUM_HARD
Tags: Constructive algorithms

Implementation

Greedy algorithms

Mathematics

Ad-hoc
Skill types: Greedy algorithms

Starter code:

Solutions:
T = int(input())
for t in range(T):
	(N, K) = input().split()
	A = list(map(int, input().split()))
	no_of_gifts = int(N)
	no_of_turns = int(K) * 2
	A.sort(reverse=True)
	lst_1 = []
	lst_2 = []
	for i in range(no_of_gifts):
		Popped_ele = A.pop(0)
		lst_1.append(Popped_ele)
		no_of_turns -= 1
		if lst_1 != []:
			Popped = A.pop(0)
			lst_2.append(Popped)
			no_of_turns -= 1
			if no_of_turns == 0:
				lst_2.append(A.pop(0))
				A = sum(lst_1)
				B = sum(lst_2)
				print(max(A, B))
				break


tc = int(input())
for _ in range(tc):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	chef1 = 0
	twin1 = 0
	while k > 0:
		chef1 += max(a)
		a.remove(max(a))
		twin1 += max(a)
		a.remove(max(a))
		if k == 1:
			twin1 += max(a)
			a.remove(max(a))
		k -= 1
	print(max(chef1, twin1))


t = int(input())
for i in range(t):
	(n, k) = list(map(int, input().split()))
	l = list(map(int, input().split()))
	l = sorted(l, reverse=True)
	a = sum(l[:2 * k:2])
	b = sum(l[1:2 * k:2]) + l[2 * k]
	print(max(a, b))


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	price = [int(x) for x in input().split()]
	duplicate = price.copy()
	duplicate.sort(reverse=True)
	turn_first = 0
	for i in range(k):
		turn_first += duplicate[2 * i]
	print(max(turn_first, sum(duplicate[:2 * k + 1]) - turn_first))


for t in range(int(input())):
	(n, k) = list(map(int, input().split()))
	a = list(map(int, input().split()))
	a.sort(reverse=1)
	f = sum(a[0:2 * k - 1:2])
	s = sum(a[1:2 * k:2]) + a[2 * k]
	if f > s:
		print(f)
	else:
		print(s)


case = int(input())
for _ in range(case):
	(n, k) = map(int, input().split(' '))
	arr = list(map(int, input().split(' ')))
	arr.sort(reverse=True)
	t1 = 0
	t2 = 0
	for i in range(n):
		if k > 0:
			if k == 1:
				if i % 2 == 0:
					t1 += arr[i]
				else:
					t2 += arr[i]
					t2 += arr[i + 1]
					k -= 1
			elif i % 2 == 0:
				t1 += arr[i]
			else:
				t2 += arr[i]
				k -= 1
		else:
			break
	print(max(t1, t2))


t = int(input())
for _ in range(t):
	(n, k) = list(map(int, input().split()))
	arr = sorted(list(map(int, input().split())), reverse=True)
	c1 = sum(arr[:2 * k:2])
	c2 = sum(arr[1:2 * k:2]) + arr[2 * k]
	print(max(c1, c2))


t = int(input())
for i in range(t):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	j = 0
	a.sort(reverse=True)
	a1 = 0
	a2 = 0
	while k > 0 and j < n:
		a1 += a[j]
		a2 += a[j + 1]
		if k == 1:
			a2 += a[j + 2]
		k -= 1
		j += 2
	print(max(a1, a2))


for _ in range(int(input())):
	(n, k) = map(int, input().split(' '))
	arr = list(map(int, input().split(' ')))
	arr.sort(reverse=True)
	rose = 0
	chef = 0
	i = 0
	k = 2 * k
	while i < n and 2 * k > 0:
		if i % 2 == 0:
			chef += arr[i]
		else:
			rose += arr[i]
		k -= 1
		i += 1
	rose = rose + arr[i]
	rose = max(chef, rose)
	print(rose)


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


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	first = []
	second = []
	a.sort(reverse=True)
	counter = 0
	for i in range(n):
		if i % 2 == 0:
			first.append(a[i])
		else:
			second.append(a[i])
			counter += 1
		if counter == k:
			second.append(a[i + 1])
			break
	print(max(sum(first), sum(second)))


t = int(input())
for i in range(t):
	(n, k) = map(int, input().split())
	z = list(map(int, input().split()))
	z = sorted(z)[::-1]
	l = 0
	m = 0
	for i in range(min(n, 2 * k)):
		if i % 2 == 0:
			l += z[i]
		else:
			m += z[i]
	if min(n, 2 * k) % 2 == 1:
		l += z[min(n, 2 * k)]
	else:
		m += z[min(n, 2 * k)]
	print(max(l, m))


for t in range(int(input())):
	(N, K) = map(int, input().split(' '))
	A = sorted(list(map(int, input().split(' '))), reverse=True)
	p1 = A[::2][:K]
	p2 = A[1::2][:K] + [A[K + K]]
	print(max(sum(p1), sum(p2)))


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


for _ in range(int(input())):
	(N, K) = list(map(int, input().split()))
	A = list(map(int, input().split()))
	A.sort(reverse=True)
	(p1, p2) = [0, A[2 * K]]
	for i in range(2 * K):
		if not bool(i % 2):
			p1 += A[i]
		else:
			p2 += A[i]
	print(max(p1, p2))


t = int(input())
for i in range(t):
	(N, K) = map(int, input().split())
	inp = list(map(int, input().strip().split()))
	chef = 0
	twin = 0
	while K > 0:
		chef += max(inp)
		inp.remove(max(inp))
		twin += max(inp)
		inp.remove(max(inp))
		K -= 1
	twin += max(inp)
	inp.remove(max(inp))
	ans = max(chef, twin)
	print(ans)


def soln(n, k, arr):
	arr.sort(reverse=True)
	s1 = s2 = 0
	for i in range(min(len(arr), k * 2)):
		if i & 1:
			s1 += arr[i]
		else:
			s2 += arr[i]
	if i & 1:
		s1 += arr[i + 1]
	else:
		s2 += arr[i + 1]
	return max(s1, s2)
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	arr = list(map(int, input().split()))
	print(soln(n, k, arr))


t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	arr = list(map(int, input().split()))
	arr = sorted(arr, reverse=True)
	x = 0
	y = 0
	for i in range(2 * k):
		if i % 2 == 0:
			x += arr[i]
		else:
			y += arr[i]
	if 2 * k < n:
		y += max(arr[2 * k:])
	print(max(x, y))


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	arr = list(map(int, input().split()))
	arr = sorted(arr, reverse=True)
	(a1, a2) = (0, 0)
	for i in range(2 * k):
		if i == 2 * k - 1:
			a2 += arr[i] + arr[i + 1]
		elif i % 2 == 0:
			a1 += arr[i]
		else:
			a2 += arr[i]
	print(max(a1, a2))


for z in range(int(input())):
	(n, k) = [int(x) for x in input().split()]
	a = [int(x) for x in input().split()]
	a.sort()
	j = 1
	p = 0
	q = 0
	for i in range(2 * k):
		if i % 2 == 0:
			p += a[n - j]
		else:
			q += a[n - j]
		j += 1
	q += a[n - j]
	print(max(p, q))


for i in range(int(input())):
	(n, m) = map(int, input().split())
	a = [int(j) for j in input().split()]
	a.sort(reverse=True)
	print(max(sum(a[:m * 2:2]), sum(a[1:m * 2:2]) + a[m * 2]))


for tc in range(int(input())):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	a.sort(reverse=True)
	c = 0
	d = a[2 * k]
	for i in range(2 * k):
		if i % 2 == 0:
			c += a[i]
		else:
			d += a[i]
	print(max(c, d))


for p in range(int(input())):
	(n, m) = map(int, input().split())
	l = list(map(int, input().split()))
	l.sort(reverse=True)
	s_1 = 0
	s_2 = 0
	i = 0
	j = 0
	while j < m:
		s_1 += l[i]
		i += 2
		j += 1
	i = 1
	j = 0
	while j < m - 1:
		s_2 += l[i]
		i += 2
		j += 1
	s_2 += l[i] + l[i + 1]
	print(max(s_1, s_2))


t = int(input())
for qw in range(t):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	a_copy = a.copy()
	chef = []
	twin = []
	chef_second = []
	twin_second = []
	c1 = 0
	c2 = 0
	for i in range(1, k * 2 + 1):
		if i == k * 2 - 1:
			z = max(a_copy)
			chef.append(z)
			a_copy.remove(z)
			z = max(a_copy)
			twin.append(z)
			a_copy.remove(z)
			z = max(a_copy)
			twin.append(z)
			a_copy.remove(z)
			break
		elif i % 2 != 0:
			chef.append(max(a_copy))
			a_copy.remove(max(a_copy))
		else:
			twin.append(max(a_copy))
			a_copy.remove(max(a_copy))
	for i in range(1, k * 2 + 1):
		if i == k * 2 - 1:
			z = max(a)
			twin_second.append(z)
			a.remove(z)
			z = max(a)
			chef_second.append(z)
			a.remove(z)
			z = max(a)
			chef_second.append(z)
			a.remove(z)
			break
		elif i % 2 != 0:
			twin_second.append(max(a))
			a.remove(max(a))
		else:
			chef_second.append(max(a))
			a.remove(max(a))
	c1 = sum(chef)
	c2 = sum(chef_second)
	if c1 >= c2:
		print(c1)
	else:
		print(c2)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	lis = list(map(int, input().split()))
	lis.sort(reverse=True)
	(ans1, ans2) = (0, lis[2 * k])
	for i in range(2 * k):
		if not i % 2:
			ans1 += lis[i]
		else:
			ans2 += lis[i]
	print(max(ans1, ans2))


import os.path
from math import gcd, floor, ceil, log2
from collections import *
import sys
mod = 1000000007
INF = float('inf')

def st():
	return list(sys.stdin.readline().strip())

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

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

def inp():
	return int(sys.stdin.readline())

def pr(n):
	return sys.stdout.write(str(n) + '\n')

def prl(n):
	return sys.stdout.write(str(n) + ' ')
if os.path.exists('input.txt'):
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')
for _ in range(int(input())):
	(n, k) = mp()
	a = li()
	a.sort(reverse=True)
	i = 0
	a1 = 0
	a2 = 0
	while k:
		if k == 1:
			a1 += a[i]
			i += 1
			a2 += a[i] + a[i + 1]
		else:
			a1 += a[i]
			i += 1
			a2 += a[i]
			i += 1
		k -= 1
	print(max(a1, a2))


t = int(input())
for l in range(t):
	(n, k) = map(int, input().split())
	arr = list(map(int, input().split()))
	arr.sort(reverse=True)
	ans1 = 0
	ans2 = 0
	i = 0
	while k:
		if k == 1:
			ans1 += arr[i]
			i += 1
			ans2 += arr[i] + arr[i + 1]
		else:
			ans1 += arr[i]
			i += 1
			ans2 += arr[i]
			i += 1
		k -= 1
	print(max(ans1, ans2))


t = int(input())
for i in range(t):
	(n, k) = list(map(int, input().split()))
	lis = list(map(int, input().split()))
	lis = sorted(lis, reverse=True)
	sum1 = sum([lis[2 * x] for x in range(0, k)])
	sum2 = sum([lis[2 * x + 1] for x in range(0, k)])
	sum2 += lis[2 * k]
	print(max(sum1, sum2))


for _ in range(int(input())):
	(n, k) = map(int, input().split(' '))
	a = list(map(int, input().split(' ')))
	chef_goes = a.copy()
	chef1 = chef2 = 0
	i = 0
	moves = 2 * k
	while i <= moves - 1:
		maxi = max(chef_goes)
		ind = chef_goes.index(maxi)
		if i % 2 == 0:
			chef1 += chef_goes.pop(ind)
		else:
			chef2 += chef_goes.pop(ind)
		i += 1
	chef2 += max(chef_goes)
	print(max(chef1, chef2))


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	a.sort(reverse=True)
	p = []
	q = []
	for i in range(2 * k):
		if i % 2 == 0:
			p.append(a[i])
		else:
			q.append(a[i])
	q.append(a[2 * k])
	print(max(sum(p), sum(q)))


a = int(input())
for i in range(a):
	(N, K) = map(int, input().split())
	A = list(map(int, input().split()))
	A.sort()
	A.reverse()
	x = 0
	y = 0
	for j in range(0, 2 * K - 1, 2):
		x += A[j]
	for j in range(1, 2 * K, 2):
		y += A[j]
	y += A[2 * K]
	if x > y:
		print(x)
	else:
		print(y)


t = int(input())
for _ in range(t):
	(n, k) = list(map(int, input().strip().split()))
	arr = list(map(int, input().strip().split()))
	arr.sort(reverse=True)
	(ans1, ans2) = (0, 0)
	i = 0
	while i < 2 * k:
		ans1 += arr[i]
		ans2 += arr[i + 1]
		i += 2
	ans2 += arr[i]
	print(max(ans1, ans2))


for x in range(int(input())):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	a.sort()
	a = a[::-1]
	a1 = 0
	a2 = a[k * 2]
	for xx in range(k * 2):
		if xx % 2 == 0:
			a1 += a[xx]
		else:
			a2 += a[xx]
	print(max(a1, a2))


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	l = sorted([int(i) for i in input().split()])
	l.reverse()
	(a, b) = (0, 0)
	t = 2 * k + 1
	for i in range(t):
		if i == t - 2 and i % 2 == 0:
			a += l[i] + l[i + 1]
			break
		elif i == t - 2 and i % 2 != 0:
			b += l[i] + l[i + 1]
			break
		if i % 2 == 0:
			a += l[i]
		else:
			b += l[i]
	if a >= b:
		print(a)
	else:
		print(b)


def Solution(N, K, A):
	if N <= 2:
		return sum(A)
	else:
		s = 0
		j = 0
		while j < 2 * K:
			s = s + A[j]
			j += 2
		L = A[:2 * K + 1]
		p = sum(L) - s
		if p >= s:
			return p
		else:
			return s
T = int(input())
for i in range(T):
	(N, K) = map(int, input().split())
	A = list(map(int, input().split()))
	A = sorted(A, reverse=True)
	result = Solution(N, K, A)
	print(result)


t = int(input())
for _ in range(t):
	(n, k) = list(map(int, input().split()))
	lst = list(map(int, input().split()))
	lst.sort(reverse=True)
	a = 0
	b = 0
	moves = 2 * k
	i = 0
	while i < 2 * k - 2:
		if i % 2 == 0:
			a += lst[i]
		else:
			b += lst[i]
		i = i + 1
	a += lst[i]
	b += lst[i + 1] + lst[i + 2]
	print(max(a, b))


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	arr = list(map(int, input().split()))
	arr.sort()
	s1 = 0
	s2 = 0
	for i in range(k):
		s1 += arr.pop()
		s2 += arr.pop()
	s2 += arr.pop()
	print(max(s1, s2))


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	a.sort()
	sum1 = 0
	sum2 = 0
	for i in range(k):
		sum1 += a.pop()
		sum2 += a.pop()
	sum2 += a[-1:][0]
	print(max(sum1, sum2))


for _ in range(int(input())):
	(n, k) = [int(a) for a in input().split()]
	arr = [int(a) for a in input().split()]
	s1 = 0
	s2 = 0
	arr.sort(reverse=True)
	i = 0
	while k > 0:
		s1 = s1 + arr[i]
		s2 = s2 + arr[i + 1]
		i = i + 2
		k = k - 1
	s2 = s2 + arr[i]
	print(max(s1, s2))


for _ in range(int(input())):
	(n, k) = [int(a) for a in input().split()]
	arr = [int(a) for a in input().split()]
	s1 = 0
	s2 = 0
	arr.sort()
	while k > 0:
		s1 = s1 + arr.pop()
		s2 = s2 + arr.pop()
		k = k - 1
	s2 = s2 + arr[-1]
	print(max(s1, s2))


from sys import stdin, stdout
import math
from collections import Counter
import functools
import time
import bisect

def tr():
	return range(int(line()))

def sm():
	return map(int, line().split())

def ln():
	return list(sm())

def nl():
	return int(line())

def ssm():
	return map(str, line().split())

def line():
	return stdin.readline().rstrip()

def b(x):
	return bin(x).replace('0b', '')

def o(x):
	if type(x) != type(''):
		x = str(x)
	stdout.write(x + '\n')

def osp(x):
	if type(x) != type(''):
		x = str(x)
	stdout.write(x + ' ')

def ol(x):
	stdout.write(' '.join(map(str, x)))

def wline():
	return stdin.read().split()

def main():
	for _ in tr():
		(n, k) = sm()
		gifts_costs = ln()
		gifts_costs.sort(reverse=True)
		first_turn = 0
		second_turn = 0
		for i in range(k):
			first_turn += gifts_costs[2 * i]
			second_turn += gifts_costs[2 * i + 1]
		second_turn += gifts_costs[2 * k]
		print(max(first_turn, second_turn))
main()


try:
	from debug import debug, timer
except ImportError:
	pass
from sys import stdin
input = stdin.readline

def rii():
	return range(int(input().strip()))

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

def mii():
	return map(int, input().strip().split(' '))

def lmii():
	return list(map(int, input().strip().split(' ')))

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

def getvals():
	while True:
		yield from input().split()

def tri(n):
	return n * (n + 1) // 2

def smallest_first(m, n):
	return (min(m, n), max(m, n))

def solve(*args):
	(n, k, a) = args
	if n % 2 == 0:
		a.pop()
	go_first = a[0:2 * k:2]
	go_second = a[1:2 * k + 1:2] + a[2 * k:2 * k + 1]
	return max(sum(go_first), sum(go_second))

def do_codechef():
	for t in rii():
		(n, k) = mii()
		a = sorted(lmii(), reverse=True)
		print(solve(n, k, a))
do_codechef()
exit()


try:
	for _ in range(int(input())):
		(n, k) = list(map(int, input().split()))
		arr = list(map(int, input().split()))
		(t, c) = (0, 0)
		i = 0
		arr.sort()
		arr = arr[::-1]
		chances = 0
		while i < n and chances < k:
			if i % 2 == 0:
				c += arr[i]
			else:
				t += arr[i]
				if k - chances == 1 and i + 1 < n:
					t += arr[i + 1]
				chances += 1
			i += 1
		print(max(t, c))
except:
	pass


for x in range(int(input())):
	(n, k) = map(int, input().split())
	li = list(map(int, input().split()))
	li = sorted(li)[::-1]
	count1 = 0
	count2 = 0
	for i in range(0, n, 2):
		count1 += li[i]
		count2 += li[i + 1]
		k -= 1
		if k == 0:
			count2 += li[i + 2]
			break
	print(max(count1, count2))


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	a.sort(reverse=True)
	chef = []
	twins = []
	for i in range(2 * k):
		if i % 2 == 0:
			chef.append(a[i])
		elif i % 2 == 1:
			twins.append(a[i])
	print(max(sum(chef), sum(twins) + a[2 * k]))


t = int(input())
for i in range(t):
	(n, k) = map(int, input().split())
	arr = list(map(int, input().split()))
	sor = list(reversed(sorted(arr)))
	a = 0
	b = 0
	ind = 0
	while k > 0 and ind < n:
		if k == 1:
			a += sor[ind]
			b += sum(sor[ind + 1:ind + 3])
		else:
			a += sor[ind]
			b += sor[ind + 1]
		ind += 2
		k -= 1
	print(max(a, b))


for _ in range(int(input())):
	(N, K) = map(int, input().split())
	listx = sorted(list(map(int, input().split())), reverse=True)
	first = []
	second = []
	for i in range(2 * K):
		if i % 2 == 0:
			first.append(listx[i])
		elif i % 2 == 1:
			second.append(listx[i])
	print(max(sum(first), sum(second) + listx[2 * K]))


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	a.sort(reverse=True)
	b = [a[i] for i in range(2 * k) if i % 2 == 0]
	c = [a[i] for i in range(2 * k) if i % 2 == 1] + [a[2 * k]]
	print(max(sum(b), sum(c)))


t = int(input())
for i in range(t):
	(n, k) = map(int, input().split())
	l = list(map(int, input().strip().split()))[:n]
	l.sort(reverse=True)
	p1 = 0
	p2 = 0
	for j in range(k):
		p1 += l[2 * j]
		p2 += l[2 * j + 1]
	p2 += l[2 * k]
	if p1 > p2:
		print(p1)
	else:
		print(p2)


T = int(input())
for tj in range(T):
	(N, K) = map(int, input().split())
	integers = list(map(int, input().split()))
	integers.sort(reverse=True)
	sum_first = 0
	sum_second = 0
	for i in range(2 * K + 1):
		if i % 2 == 0 and i != 2 * K:
			sum_first += integers[i]
		else:
			sum_second += integers[i]
	print(max(sum_first, sum_second))


t = int(input())
for _ in range(t):
	(n, k) = [int(x) for x in input().split()]
	L = [int(x) for x in input().split()]
	L.sort()
	L1 = L[-1:-k * 2:-2]
	L2 = L[-2:-k * 2 - 1:-2]
	L2 += [L[-(k * 2) - 1]]
	print(max(sum(L1), sum(L2)))


from math import *
import sys

def input():
	return sys.stdin.readline().replace('\n', '').strip()
sys.setrecursionlimit(10 ** 9)
for _ in range(int(input())):
	(n, k) = list(map(int, input().split()))
	l = list(map(int, input().split()))
	l.sort()
	l1 = l[-1:-k * 2:-2]
	l2 = l[-2:-k * 2 - 1:-2]
	l2 += [l[-(k * 2) - 1]]
	print(max(sum(l1), sum(l2)))


for i in range(int(input())):
	(n, k) = [int(i) for i in input().split()]
	l = [int(i) for i in input().split()]
	l = sorted(l, reverse=True)
	s1 = 0
	s2 = 0
	i = 0
	j = 2 * k
	while j != 0:
		if i == 0:
			s1 += l[0]
			i = 1
			l.pop(0)
		else:
			s2 += l[0]
			i = 0
			l.pop(0)
		j -= 1
	s2 += l[0]
	print(max(s1, s2))


tc = int(input())
while tc > 0:
	(n, k) = map(int, input().split())
	arr = list(map(int, input().split()))
	sum1 = 0
	sum2 = 0
	arr.sort(reverse=True)
	for i in range(k):
		sum1 += arr[2 * i]
		sum2 += arr[2 * i + 1]
	if n > 2 * k:
		sum2 += arr[2 * k]
	print(max(sum1, sum2))
	tc -= 1


for _ in range(int(input())):
	(a, b) = map(int, input().split())
	(c, d) = (0, 0)
	k = list(map(int, input().split()))
	g = len(k)
	k.sort(reverse=True)
	for i in range(b):
		c += k[2 * i]
		d += k[2 * i + 1]
	if a >= 2 * b + 1:
		d += k[2 * b]
	print(max(c, d))


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	x = sorted(list(map(int, input().split())), reverse=True)
	a = b = 0
	for i in range(k):
		a += x[2 * i]
		b += x[2 * i + 1]
	if n >= 2 * k + 1:
		b += x[2 * k]
	print(max(a, b))


for i in range(int(input())):
	(n, k) = list(map(int, input().split()))
	a = list(map(int, input().split()))
	a.sort()
	a.reverse()
	first = 0
	second = 0
	for j in range(2 * k):
		if j % 2 == 0:
			first = first + a[j]
		else:
			second = second + a[j]
	second = second + a[j + 1]
	print(max(first, second))


for i in range(int(input())):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	a.sort()
	a.reverse()
	s1 = 0
	s2 = 0
	c1 = k
	c2 = k
	for i in range(0, len(a)):
		if i % 2 == 0:
			s1 += a[i]
			c1 -= 1
		if c1 == 0:
			break
	for i in range(len(a)):
		if i % 2 != 0:
			s2 += a[i]
			c2 -= 1
		if c2 == 0:
			s2 += a[i + 1]
			break
	print(max(s1, s2))


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	a.sort(reverse=True)
	a = a[:2 * k + 1]
	r = 0
	i = 0
	s1 = 0
	while r < k:
		s1 += a[i]
		i += 2
		r += 1
	print(max(s1, sum(a) - s1))


for q in range(int(input())):
	(n, k) = map(int, input().split())
	li = [int(i) for i in input().split()]
	option1 = 0
	option2 = 0
	sum1 = 0
	sum2 = 0
	li.sort(reverse=True)
	a = 0
	for i in range(len(li)):
		if i % 2 == 0 and option1 != k:
			sum1 += li[i]
			option1 += 1
		elif i % 2 != 0:
			sum2 += li[i]
			option2 += 1
		if option2 == k:
			break
	if i != n - 1:
		sum2 += li[i + 1]
	print(max(sum1, sum2))


for i in range(int(input())):
	(n, k) = map(int, input().split())
	n_lst = list(map(int, input().split()))
	n_lst.sort()
	st = 0
	nd = 0
	n -= 1
	for i in range(k):
		st += n_lst[n]
		if i + 1 == k:
			nd += n_lst[n - 1] + n_lst[n - 2]
		else:
			nd += n_lst[n - 1]
		n -= 2
	print(max(st, nd))


for i in range(int(input())):
	(n, k) = [int(x) for x in input().split()]
	nums = [int(x) for x in input().split()]
	nums.sort(reverse=True)
	count = 0
	count1 = 0
	for j in range(k * 2):
		if j == k * 2 - 1:
			count1 += nums[j] + nums[j + 1]
			break
		if j % 2 == 0:
			count += nums[j]
		else:
			count1 += nums[j]
	print(max(count, count1))