You are given an array $a$ of $n$ integers, and another integer $k$ such that $2k \le n$.

You have to perform exactly $k$ operations with this array. In one operation, you have to choose two elements of the array (let them be $a_i$ and $a_j$; they can be equal or different, but their positions in the array must not be the same), remove them from the array, and add $\lfloor \frac{a_i}{a_j} \rfloor$ to your score, where $\lfloor \frac{x}{y} \rfloor$ is the maximum integer not exceeding $\frac{x}{y}$.

Initially, your score is $0$. After you perform exactly $k$ operations, you add all the remaining elements of the array to the score.

Calculate the minimum possible score you can get.


-----Input-----

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

Each test case consists of two lines. The first line contains two integers $n$ and $k$ ($1 \le n \le 100$; $0 \le k \le \lfloor \frac{n}{2} \rfloor$).

The second line contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 2 \cdot 10^5$).


-----Output-----

Print one integer — the minimum possible score you can get.


-----Examples-----

Input
5
7 3
1 1 1 2 1 3 1
5 1
5 5 5 5 5
4 2
1 3 3 7
2 0
4 2
9 2
1 10 10 1 10 2 7 10 3
Output
2
16
0
6
16


-----Note-----

Let's consider the example test.

In the first test case, one way to obtain a score of $2$ is the following one:

choose $a_7 = 1$ and $a_4 = 2$ for the operation; the score becomes $0 + \lfloor \frac{1}{2} \rfloor = 0$, the array becomes $[1, 1, 1, 1, 3]$;

choose $a_1 = 1$ and $a_5 = 3$ for the operation; the score becomes $0 + \lfloor \frac{1}{3} \rfloor = 0$, the array becomes $[1, 1, 1]$;

choose $a_1 = 1$ and $a_2 = 1$ for the operation; the score becomes $0 + \lfloor \frac{1}{1} \rfloor = 1$, the array becomes $[1]$;

add the remaining element $1$ to the score, so the resulting score is $2$.

In the second test case, no matter which operations you choose, the resulting score is $16$.

In the third test case, one way to obtain a score of $0$ is the following one:

choose $a_1 = 1$ and $a_2 = 3$ for the operation; the score becomes $0 + \lfloor \frac{1}{3} \rfloor = 0$, the array becomes $[3, 7]$;

choose $a_1 = 3$ and $a_2 = 7$ for the operation; the score becomes $0 + \lfloor \frac{3}{7} \rfloor = 0$, the array becomes empty;

the array is empty, so the score doesn't change anymore.

In the fourth test case, no operations can be performed, so the score is the sum of the elements of the array: $4 + 2 = 6$.

Difficulty: EASY
Tags: Dynamic programming

Mathematics

Greedy algorithms
Skill types: Dynamic programming

Greedy algorithms

Starter code:

Solutions:
t = int(input())
for _ in range(t):
	(n, k) = [int(x) for x in input().split()]
	arr = [int(x) for x in input().split()]
	arr.sort(reverse=True)
	(i, j) = (0, k)
	ans = 0
	while k:
		ans += arr[j] // arr[i]
		k -= 1
		i += 1
		j += 1
	for indx in range(j, n):
		ans += arr[indx]
	print(ans)


import sys
inpu = sys.stdin.readline
prin = sys.stdout.write
import math
t = int(inpu())
for _ in range(t):
	(n, k) = map(int, inpu().split())
	a = list(map(int, inpu().split()))
	a.sort()
	score = sum(a[:n - 2 * k])
	left = a[-2 * k:]
	for i in range(k):
		score += left[i] // left[i + k]
	print(score)


tt = int(input())
for _ in range(tt):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	a.sort()
	cnt = 0
	was = [0] * n
	for i in range(n - 1, n - k - 1, -1):
		was[i] = 1
		was[i - k] = 1
		cnt += a[i - k] // a[i]
	for i in range(n):
		if was[i] == 0:
			cnt += a[i]
	print(cnt)


for _ in range(int(input())):
	dic = {}
	(n, k) = map(int, input().split())
	arr = list(map(int, input().split()))
	arr.sort()
	score = sum(arr[:n - 2 * k])
	dic = {}
	for el in arr[n - 2 * k:]:
		if el not in dic:
			dic[el] = 1
		else:
			dic[el] += 1
	keys = list(dic.keys())
	tmax = 0
	psum = 0
	for k in range(len(keys)):
		if dic[keys[k]] > tmax:
			tmax = dic[keys[k]]
		psum += dic[keys[k]]
	if 2 * tmax > psum:
		score += (2 * tmax - psum) // 2
	print(score)


t = int(input())
for i in range(0, t):
	(n, k) = map(int, input().split())
	b = list(map(int, input().split()))
	b.sort()
	if k > 0:
		prev = b[n - 2 * k]
		same = 1
		maxs = 1
		for j in range(n - 2 * k + 1, n):
			if b[j] == prev:
				same += 1
			else:
				same = 1
			prev = b[j]
			maxs = max(maxs, same)
		if maxs <= k:
			print(sum(b[:n - 2 * k]))
		else:
			print(sum(b[:n - 2 * k]) + (maxs - k))
	else:
		print(sum(b))


import math
t = int(input())
for i in range(t):
	(n, k) = [int(i) for i in input().split()]
	arr = [int(i) for i in input().split()]
	arr.sort()
	op = sum([math.floor(arr[n - k * 2 + j] / arr[n - k + j]) for j in range(k)])
	rem = sum(arr[:n - k * 2])
	score = op + rem
	print(score)


for j in range(int(input())):
	(n, k) = list(map(int, input().split()))
	arr = list(map(int, input().split()))
	arr.sort()
	rem = k
	ans = 0
	while rem > 0:
		ma = max(arr)
		cnt = arr.count(ma)
		if cnt > rem:
			ans += 1
			arr.pop()
			arr.pop()
		else:
			ind = arr.index(ma)
			ans += 0
			arr.pop(ind - rem)
			arr.pop()
		rem -= 1
	ans += sum(arr)
	print(ans)


from math import floor
tc = int(input())
for case in range(tc):
	(n, k) = (int(i) for i in input().split())
	numbers = [int(j) for j in input().split()]
	numbers = sorted(numbers)
	to_erase = numbers[-2 * k:]
	suma = sum(numbers[:n - 2 * k])
	my_dict = dict()
	for num in to_erase:
		try:
			my_dict[num] += 1
		except:
			my_dict[num] = 1
	max_value = max(my_dict.values())
	restantes = 2 * k - max_value
	faltan = max(max_value - restantes, 0)
	para_sumar = faltan // 2
	total = suma + para_sumar
	print(suma) if k == 0 else print(total)


import math
for _ in range(int(input())):
	(n, k) = list(map(int, input().split()))
	a = list(map(int, input().split()))
	a.sort(reverse=True)
	if k == 0:
		print(sum(a))
	else:
		s = 0
		for i in range(k):
			s += a[i + k] // a[i]
		summ = 0
		for i in range(2 * k, n):
			summ += a[i]
		print(s + summ)


import math

def quck_sort(lst, start, end):
	if start >= end:
		return
	left = start
	right = end
	mid = lst[left]
	while left < right:
		while left < right and lst[right] <= mid:
			right -= 1
		lst[left] = lst[right]
		while left < right and lst[left] > mid:
			left += 1
		lst[right] = lst[left]
	lst[left] = mid
	quck_sort(lst, start, left - 1)
	quck_sort(lst, left + 1, end)

def solve(n, L):
	ans = 0
	quck_sort(L, 0, len(L) - 1)
	for i in range(0, n):
		ans += math.floor(L[n + i] / L[i])
	for i in range(2 * n, len(L)):
		ans += L[i]
	print(ans)
for _ in range(int(input())):
	nk = list(map(int, input().split(' ')))
	n = nk[0]
	k = nk[1]
	L = list(map(int, input().split(' ')))
	solve(k, L)


import sys
input = lambda : sys.stdin.readline().rstrip()

def solve():
	T = int(input())
	for t in range(T):
		(n, k) = list(map(int, input().split()))
		nums = map(int, input().split())
		nums = sorted(nums)
		(nomr, denomr) = (n - 2 * k, n - k)
		score = 0
		i = 0
		while i < nomr:
			score += nums[i]
			i += 1
		while denomr < n:
			score += nums[nomr] // nums[denomr]
			nomr += 1
			denomr += 1
		print(score)
solve()


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	a = [int(x) for x in input().split()]
	a = sorted(a)
	cost = sum(a[0:n - 2 * k]) + sum(map(lambda x: a[x + n - 2 * k] // a[x + n - k], range(0, k)))
	print(cost)


from collections import defaultdict
t = int(input())
for _ in range(t):
	(n, k) = list(map(int, input().strip().split()))
	x = list(map(int, input().strip().split()))
	ans = 0
	if k > 0:
		x.sort(reverse=True)
		dic = defaultdict(int)
		for i in range(2 * k):
			dic[x[i]] += 1
		maxx = max(dic.values())
		ans += max((2 * maxx - sum(dic.values())) // 2, 0)
	ans += sum(x[2 * k:])
	print(ans)


for _ in range(int(input())):
	(s, k) = [int(_) for _ in input().split()]
	a = [int(_) for _ in input().split()]
	if k == 0:
		print(sum(a))
	else:
		r = 0
		a.sort()
		header = a[s - 2 * k:s - k]
		tail = a[s - k:]
		for _ in zip(header, tail):
			r += _[0] // _[1]
		r += sum(a[:s - 2 * k])
		print(r)


from math import gcd
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	arr = list(map(int, input().split()))
	if k == 0:
		print(sum(arr))
		continue
	arr.sort()
	arr1 = arr[-2 * k:-k]
	arr2 = arr[-k:]
	arr3 = arr[:-2 * k]
	ans = 0
	for _ in range(k):
		ans += arr1.pop() // arr2.pop()
	ans += sum(arr3)
	print(ans)


t = int(input())
for ii in range(t):
	(n, k) = map(int, input().split())
	l = list(map(int, input().split()))
	l.sort()
	m = l[n - 2 * k:]
	freq = {}
	max_f = 0
	for i in m:
		freq[i] = freq.get(i, 0) + 1
		if freq[i] > max_f:
			max_f = freq[i]
	ans = 0
	if max_f > k:
		ans = max_f - k
	if 2 * k < n:
		s = sum(l[:n - 2 * k])
		print(s + ans)
	else:
		print(ans)


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


from bisect import bisect_left as bl
from bisect import bisect_right as br
from heapq import heappush, heappop
import math
from collections import *
from functools import reduce, cmp_to_key, lru_cache
import io, os
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
M = mod = 998244353

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

def inv_mod(n):
	return pow(n, mod - 2, mod)

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

def st():
	return str(input().rstrip())[2:-1]

def val():
	return int(input().rstrip())

def li2():
	return [str(i)[2:-1] for i in input().rstrip().split()]

def li3():
	return [int(i) for i in st()]
for _ in range(val()):
	(n, k) = li()
	l = sorted(li())
	ans = 0
	if k:
		cnt = Counter(l[-(2 * k):])
		ma = max(cnt.values())
		ans = max(0, ma - k)
	ans += sum(l[:n - 2 * k])
	print(ans)


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


from sys import stdin
import math
from collections import deque
from heapq import heapify, heappop, heappush
from bisect import bisect_left, bisect_right
input = stdin.readline
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	arr = sorted(list(map(int, input().split())))
	if len(set(arr)) == 1:
		print(k + arr[-1] * (n - 2 * k))
		continue
	if k == 0:
		print(sum(arr))
		continue
	val = sum(arr[:n - 2 * k])
	(i, j) = (n - k - 1, n - k)
	if arr[i] != arr[j]:
		print(val)
		continue
	(left, right) = (0, 0)
	for b in range(j, n):
		if arr[b] == arr[j]:
			right += 1
		else:
			break
	for b in range(i, max(-1, i - k), -1):
		if arr[b] == arr[i]:
			left += 1
		else:
			break
	if k - right < left:
		val += left - k + right
	print(val)


def solve(li, n, k):
	li.sort()
	score = sum(li[:n - 2 * k])
	for i in range(n - 2 * k, n - k):
		score += li[i] // li[i + k]
	return score
for case in range(int(input())):
	(n, k) = map(int, input().split())
	li = list(map(int, input().split()))
	ans = solve(li, n, k)
	print(ans)


from sys import stdin
input = stdin.buffer.readline

def func():
	rem = k
	a.sort(reverse=True)
	for i in range(n):
		if rem == 0:
			break
		if a[i + k] != a[i]:
			a[i] = a[i + k] = 0
		else:
			a[i] = 0
			a[i + k] = 1
		rem -= 1
	print(sum(a))
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	func()


def solve():
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	a = sorted(a)
	cost = sum(a[0:n - 2 * k]) + sum(map(lambda x: a[x + n - 2 * k] // a[x + n - k], range(0, k)))
	print(cost)
t = int(input())
for i in range(t):
	solve()


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


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

def get():
	return int(input())

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

def S():
	for test in range(int(input())):
		solve()
import math
import itertools as it
import bisect
import time
import collections as ct

def lower_bound(a, x):
	l = -1
	r = len(a)
	while l + 1 != r:
		mid = l + r >> 1
		if a[mid] < x:
			l = mid
		else:
			r = mid
	return r

def upper_bound(a, x):
	l = -1
	r = len(a)
	while l + 1 != r:
		mid = l + r >> 1
		if a[mid] <= x:
			l = mid
		else:
			r = mid
	return r

def solve():
	(n, k) = getint()
	s = n - 2 * k
	a = getint()
	a.sort()
	ans = 0
	for i in range(s):
		ans += a.pop(0)
	dic = {}
	for i in range(len(a)):
		dic[a[i]] = dic.get(a[i], 0) + 1
	m = 0
	for (i, j) in dic.items():
		m = max(m, j)
	ans += max(0, (m - (k * 2 - m)) // 2)
	print(ans)
S()


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

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

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

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

def sinp(n=1):
	if n == 1:
		return stdin.readline().strip()
	elif n == 2:
		return list(stdin.readline().strip())
	else:
		return list(stdin.readline().split())

def pr(*x, end='\n'):
	print(*x, end=end)

def mod(f, val=1000000007):
	return f % val

def csort(c):
	sorted(c.items(), key=lambda pair: pair[1], reverse=True)

def indc(l, n):
	c = {}
	for i in range(n):
		c[l[i]] = c.get(l[i], []) + [i + 1]
	return c
cou = inp()
for _ in range(cou):
	(n, k) = vinp()
	l = linp()
	l.sort(reverse=True)
	s = sum(l[2 * k:])
	for i in range(k):
		s += int(l[k + i] // l[i])
	pr(s)


from fractions import gcd as hcf
t = int(input())
for _t in range(t):
	(n, k) = map(int, input().split())
	s = [int(x) for x in input().split()]
	s.sort()
	if k != 0:
		fp = s[:-(2 * k)]
		sp = s[-(2 * k):]
	else:
		fp = s
		sp = []
	sp_score = 0
	for i in range(k):
		sp_score += sp[i] // sp[i + k]
	print(sum(fp) + sp_score)


for case in range(int(input())):
	(n, k) = [int(x) for x in input().split()]
	arr = [int(x) for x in input().split()]
	arr.sort()
	ans = 0
	i = 0
	j1 = n - 2 * k
	j2 = n - k
	for i in range(j1):
		ans += arr[i]
	for i in range(k):
		ans += arr[j1] // arr[j2]
		j1 += 1
		j2 += 1
	print(ans)


ans = []
t = int(input())
for x in range(t):
	score = 0
	(n, k) = input().split()
	(n, k) = (int(n), int(k))
	lst = sorted(list(map(int, input().split())))
	if k > 0:
		zn = lst[-k:]
		lst = lst[:-k]
		ch = lst[-k:]
		lst = lst[:-k]
		q = 0
		while q < len(ch):
			score += ch[q] // zn[q]
			q += 1
	score += sum(lst)
	ans.append(score)
for x in ans:
	print(x)


def doSomething(arr, k):
	l = len(arr)
	arr.sort()
	k_arr = arr[l - 2 * k:]
	rem_arr = arr[:l - 2 * k]
	sum = 0
	for i in rem_arr:
		sum += i
	a = k_arr[:k]
	b = k_arr[k:]
	for i in range(k):
		sum += int(a[i] / b[i])
	print(sum)
t = int(input())
for i in range(t):
	(n, k) = list(map(int, input().split()))
	array = list(map(int, input().split()))
	doSomething(array, k)


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


from collections import Counter
import collections
t = int(input())
for _ in range(t):
	(n, k) = list(map(int, input().split()))
	arr = list(map(int, input().split()))
	ans = 0
	arr.sort()
	if k == 0:
		print(sum(arr))
		continue
	retained = n - 2 * k
	for i in range(retained):
		ans += arr[i]
	c = Counter(arr[retained:])
	freq = max(list(c.values()))
	if freq > k:
		ans += freq - k
	print(ans)


from __future__ import division, print_function
import math
import sys
import os
from io import BytesIO, IOBase
from typing import Counter
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))
input = lambda : sys.stdin.readline().rstrip('\r\n')

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

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

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

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

def invr():
	return map(int, input().split())
for _ in range(inp()):
	(n, k) = invr()
	l = inlt()
	l.sort()
	ans = sum(l[:n - 2 * k])
	temp = l[n - 2 * k:]
	(i, j) = (0, len(temp) - 1)
	g = Counter(temp)
	for each in g:
		if g[each] > len(temp) // 2:
			ans += (2 * g[each] - len(temp)) // 2
	print(ans)


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


t = int(input())
ret = []
from collections import deque
from itertools import groupby
for ii in range(t):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	a.sort(reverse=True)
	A = a[:k]
	B = a[k:2 * k]
	C = a[2 * k:]
	LA = [len(list(group)) for (key, group) in groupby(A)]
	LB = [len(list(group)) for (key, group) in groupby(B)]
	score = 0
	if a[k - 1] == a[k]:
		try:
			if LA[-1] + LB[0] > k:
				score += LA[-1] + LB[0] - k
		except:
			pass
	score += sum(C)
	ret.append(score)
print(*ret, sep='\n')


import os
import sys
import math
from io import BytesIO, IOBase
import io
from fractions import Fraction
import collections
from itertools import permutations
from collections import defaultdict
from collections import deque
from collections import Counter
import threading
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')

class SegmentTree:

	def __init__(self, data, default=10 ** 18, func=lambda a, b: min(a, b)):
		self._default = default
		self._func = func
		self._len = len(data)
		self._size = _size = 1 << (self._len - 1).bit_length()
		self.data = [default] * (2 * _size)
		self.data[_size:_size + self._len] = data
		for i in reversed(range(_size)):
			self.data[i] = func(self.data[i + i], self.data[i + i + 1])

	def __delitem__(self, idx):
		self[idx] = self._default

	def __getitem__(self, idx):
		return self.data[idx + self._size]

	def __setitem__(self, idx, value):
		idx += self._size
		self.data[idx] = value
		idx >>= 1
		while idx:
			self.data[idx] = self._func(self.data[2 * idx], self.data[2 * idx + 1])
			idx >>= 1

	def __len__(self):
		return self._len

	def query(self, start, stop):
		if start == stop:
			return self.__getitem__(start)
		stop += 1
		start += self._size
		stop += self._size
		res = self._default
		while start < stop:
			if start & 1:
				res = self._func(res, self.data[start])
				start += 1
			if stop & 1:
				stop -= 1
				res = self._func(res, self.data[stop])
			start >>= 1
			stop >>= 1
		return res

	def __repr__(self):
		return 'SegmentTree({0})'.format(self.data)

class SegmentTree1:

	def __init__(self, data, default=0, func=lambda a, b: a + b):
		self._default = default
		self._func = func
		self._len = len(data)
		self._size = _size = 1 << (self._len - 1).bit_length()
		self.data = [default] * (2 * _size)
		self.data[_size:_size + self._len] = data
		for i in reversed(range(_size)):
			self.data[i] = func(self.data[i + i], self.data[i + i + 1])

	def __delitem__(self, idx):
		self[idx] = self._default

	def __getitem__(self, idx):
		return self.data[idx + self._size]

	def __setitem__(self, idx, value):
		idx += self._size
		self.data[idx] = value
		idx >>= 1
		while idx:
			self.data[idx] = self._func(self.data[2 * idx], self.data[2 * idx + 1])
			idx >>= 1

	def __len__(self):
		return self._len

	def query(self, start, stop):
		if start == stop:
			return self.__getitem__(start)
		stop += 1
		start += self._size
		stop += self._size
		res = self._default
		while start < stop:
			if start & 1:
				res = self._func(res, self.data[start])
				start += 1
			if stop & 1:
				stop -= 1
				res = self._func(res, self.data[stop])
			start >>= 1
			stop >>= 1
		return res

	def __repr__(self):
		return 'SegmentTree({0})'.format(self.data)
MOD = 10 ** 9 + 7

class Factorial:

	def __init__(self, MOD):
		self.MOD = MOD
		self.factorials = [1, 1]
		self.invModulos = [0, 1]
		self.invFactorial_ = [1, 1]

	def calc(self, n):
		if n <= -1:
			print('Invalid argument to calculate n!')
			print('n must be non-negative value. But the argument was ' + str(n))
			exit()
		if n < len(self.factorials):
			return self.factorials[n]
		nextArr = [0] * (n + 1 - len(self.factorials))
		initialI = len(self.factorials)
		prev = self.factorials[-1]
		m = self.MOD
		for i in range(initialI, n + 1):
			prev = nextArr[i - initialI] = prev * i % m
		self.factorials += nextArr
		return self.factorials[n]

	def inv(self, n):
		if n <= -1:
			print('Invalid argument to calculate n^(-1)')
			print('n must be non-negative value. But the argument was ' + str(n))
			exit()
		p = self.MOD
		pi = n % p
		if pi < len(self.invModulos):
			return self.invModulos[pi]
		nextArr = [0] * (n + 1 - len(self.invModulos))
		initialI = len(self.invModulos)
		for i in range(initialI, min(p, n + 1)):
			next = -self.invModulos[p % i] * (p // i) % p
			self.invModulos.append(next)
		return self.invModulos[pi]

	def invFactorial(self, n):
		if n <= -1:
			print('Invalid argument to calculate (n^(-1))!')
			print('n must be non-negative value. But the argument was ' + str(n))
			exit()
		if n < len(self.invFactorial_):
			return self.invFactorial_[n]
		self.inv(n)
		nextArr = [0] * (n + 1 - len(self.invFactorial_))
		initialI = len(self.invFactorial_)
		prev = self.invFactorial_[-1]
		p = self.MOD
		for i in range(initialI, n + 1):
			prev = nextArr[i - initialI] = prev * self.invModulos[i % p] % p
		self.invFactorial_ += nextArr
		return self.invFactorial_[n]

class Combination:

	def __init__(self, MOD):
		self.MOD = MOD
		self.factorial = Factorial(MOD)

	def ncr(self, n, k):
		if k < 0 or n < k:
			return 0
		k = min(k, n - k)
		f = self.factorial
		return f.calc(n) * f.invFactorial(max(n - k, k)) * f.invFactorial(min(k, n - k)) % self.MOD
mod = 10 ** 9 + 7
omod = 998244353
prime = [True for i in range(10001)]
prime[0] = prime[1] = False

def SieveOfEratosthenes(n=10000):
	p = 2
	c = 0
	while p <= n:
		if prime[p] == True:
			c += 1
			for i in range(p * p, n + 1, p):
				prime[i] = False
		p += 1

class DSU:

	def __init__(self, R, C):
		self.par = range(R * C + 1)
		self.rnk = [0] * (R * C + 1)
		self.sz = [1] * (R * C + 1)

	def find(self, x):
		if self.par[x] != x:
			self.par[x] = self.find(self.par[x])
		return self.par[x]

	def union(self, x, y):
		(xr, yr) = (self.find(x), self.find(y))
		if xr == yr:
			return
		if self.rnk[xr] < self.rnk[yr]:
			(xr, yr) = (yr, xr)
		if self.rnk[xr] == self.rnk[yr]:
			self.rnk[xr] += 1
		self.par[yr] = xr
		self.sz[xr] += self.sz[yr]

	def size(self, x):
		return self.sz[self.find(x)]

	def top(self):
		return self.size(len(self.sz) - 1) - 1

class LazySegTree:

	def __init__(self, _op, _e, _mapping, _composition, _id, v):

		def set(p, x):
			assert 0 <= p < _n
			p += _size
			for i in range(_log, 0, -1):
				_push(p >> i)
			_d[p] = x
			for i in range(1, _log + 1):
				_update(p >> i)

		def get(p):
			assert 0 <= p < _n
			p += _size
			for i in range(_log, 0, -1):
				_push(p >> i)
			return _d[p]

		def prod(l, r):
			assert 0 <= l <= r <= _n
			if l == r:
				return _e
			l += _size
			r += _size
			for i in range(_log, 0, -1):
				if l >> i << i != l:
					_push(l >> i)
				if r >> i << i != r:
					_push(r >> i)
			sml = _e
			smr = _e
			while l < r:
				if l & 1:
					sml = _op(sml, _d[l])
					l += 1
				if r & 1:
					r -= 1
					smr = _op(_d[r], smr)
				l >>= 1
				r >>= 1
			return _op(sml, smr)

		def apply(l, r, f):
			assert 0 <= l <= r <= _n
			if l == r:
				return
			l += _size
			r += _size
			for i in range(_log, 0, -1):
				if l >> i << i != l:
					_push(l >> i)
				if r >> i << i != r:
					_push(r - 1 >> i)
			l2 = l
			r2 = r
			while l < r:
				if l & 1:
					_all_apply(l, f)
					l += 1
				if r & 1:
					r -= 1
					_all_apply(r, f)
				l >>= 1
				r >>= 1
			l = l2
			r = r2
			for i in range(1, _log + 1):
				if l >> i << i != l:
					_update(l >> i)
				if r >> i << i != r:
					_update(r - 1 >> i)

		def _update(k):
			_d[k] = _op(_d[2 * k], _d[2 * k + 1])

		def _all_apply(k, f):
			_d[k] = _mapping(f, _d[k])
			if k < _size:
				_lz[k] = _composition(f, _lz[k])

		def _push(k):
			_all_apply(2 * k, _lz[k])
			_all_apply(2 * k + 1, _lz[k])
			_lz[k] = _id
		_n = len(v)
		_log = _n.bit_length()
		_size = 1 << _log
		_d = [_e] * (2 * _size)
		_lz = [_id] * _size
		for i in range(_n):
			_d[_size + i] = v[i]
		for i in range(_size - 1, 0, -1):
			_update(i)
		self.set = set
		self.get = get
		self.prod = prod
		self.apply = apply
MIL = 1 << 20

def makeNode(total, count):
	return total * MIL + count

def getTotal(node):
	return math.floor(node / MIL)

def getCount(node):
	return node - getTotal(node) * MIL
nodeIdentity = makeNode(0.0, 0.0)

def nodeOp(node1, node2):
	return node1 + node2
	return makeNode(getTotal(node1) + getTotal(node2), getCount(node1) + getCount(node2))
identityMapping = -1

def mapping(tag, node):
	if tag == identityMapping:
		return node
	count = getCount(node)
	return makeNode(tag * count, count)

def composition(mapping1, mapping2):
	return mapping1 if mapping1 != identityMapping else mapping2

class LazySegUpdate:

	def __init__(self, N):
		self.N = N
		n = 4 * N
		self.tree = [0] * n
		self.lazy = [0] * n

	def queryHelper(self, index, s, e, l, r):
		if self.lazy[index]:
			update = self.lazy[index]
			self.lazy[index] = 0
			self.tree[index] = max(self.tree[index], update)
			if s != e:
				self.lazy[2 * index] = max(self.lazy[2 * index], update)
				self.lazy[2 * index + 1] = max(self.lazy[2 * index + 1], update)
		if s > e or s > r or e < l:
			return 0
		if s >= l and e <= r:
			return self.tree[index]
		mid = (s + e) // 2
		return max(self.queryHelper(2 * index, s, mid, l, r), self.queryHelper(2 * index + 1, mid + 1, e, l, r))

	def updateHelper(self, index, s, e, l, r, h):
		if self.lazy[index]:
			update = self.lazy[index]
			self.lazy[index] = 0
			self.tree[index] = max(self.tree[index], update)
			if s != e:
				self.lazy[2 * index] = max(self.lazy[2 * index], update)
				self.lazy[2 * index + 1] = max(self.lazy[2 * index + 1], update)
		if s > e or s > r or e < l:
			return
		if s >= l and e <= r:
			self.tree[index] = max(self.tree[index], h)
			if s != e:
				self.lazy[2 * index] = max(self.lazy[2 * index], h)
				self.lazy[2 * index + 1] = max(self.lazy[2 * index + 1], h)
			return
		mid = (s + e) // 2
		self.updateHelper(2 * index, s, mid, l, r, h)
		self.updateHelper(2 * index + 1, mid + 1, e, l, r, h)
		self.tree[index] = max(self.tree[2 * index], self.tree[2 * index + 1])

	def query(self, l, r):
		return self.queryHelper(1, 0, self.N - 1, l, r - 1)

	def update(self, l, r, h):
		self.updateHelper(1, 0, self.N - 1, l, r - 1, h)

def memodict(f):

	class memodict(dict):

		def __missing__(self, key):
			ret = self[key] = f(key)
			return ret
	return memodict().__getitem__

def pollard_rho(n):
	if n & 1 == 0:
		return 2
	if n % 3 == 0:
		return 3
	s = (n - 1 & 1 - n).bit_length() - 1
	d = n >> s
	for a in [2, 325, 9375, 28178, 450775, 9780504, 1795265022]:
		p = pow(a, d, n)
		if p == 1 or p == n - 1 or a % n == 0:
			continue
		for _ in range(s):
			prev = p
			p = p * p % n
			if p == 1:
				return math.gcd(prev - 1, n)
			if p == n - 1:
				break
		else:
			for i in range(2, n):
				(x, y) = (i, (i * i + 1) % n)
				f = math.gcd(abs(x - y), n)
				while f == 1:
					(x, y) = ((x * x + 1) % n, (y * y + 1) % n)
					y = (y * y + 1) % n
					f = math.gcd(abs(x - y), n)
				if f != n:
					return f
	return n

@memodict
def prime_factors(n):
	if n <= 1:
		return Counter()
	f = pollard_rho(n)
	return Counter([n]) if f == n else prime_factors(f) + prime_factors(n // f)

def distinct_factors(n):
	factors = [1]
	for (p, exp) in prime_factors(n).items():
		factors += [p ** i * factor for factor in factors for i in range(1, exp + 1)]
	return factors

def all_factors(n):
	(small, large) = ([], [])
	for i in range(1, int(n ** 0.5) + 1, 2 if n & 1 else 1):
		if not n % i:
			small.append(i)
			large.append(n // i)
	if small[-1] == large[-1]:
		large.pop()
	large.reverse()
	small.extend(large)
	return small

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))

def binarySearch(arr, n, key):
	left = 0
	right = n - 1
	mid = 0
	res = n
	while left <= right:
		mid = (right + left) // 2
		if arr[mid] >= key:
			res = mid
			right = mid - 1
		else:
			left = mid + 1
	return res

def binarySearch1(arr, n, key):
	left = 0
	right = n - 1
	mid = 0
	res = -1
	while left <= right:
		mid = (right + left) // 2
		if arr[mid] > key:
			right = mid - 1
		else:
			res = mid
			left = mid + 1
	return res
tt = 1
tt = int(input())
for _ in range(tt):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	a.sort(reverse=True)
	ans = sum(a[2 * k:])
	d = defaultdict(int)
	ch = 0
	for i in range(2 * k):
		d[a[i]] += 1
		if d[a[i]] > k:
			ch += 1
	ans += ch
	print(ans)


for i in range(int(input())):
	(n, k) = map(int, input().split())
	a = [int(j) for j in input().split()]
	a.sort(reverse=True)
	ans = 0
	for j in range(n):
		if j >= 2 * k:
			ans += a[j]
		elif j < k:
			ans += a[j + k] // a[j]
	print(ans)


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


from collections import Counter, defaultdict, deque
import bisect
from sys import stdin, stdout
from itertools import repeat
import math

def inp(force_list=False):
	re = list(map(int, input().split()))
	if len(re) == 1 and (not force_list):
		return re[0]
	return re

def inst():
	return input().strip()

def gcd(x, y):
	while y:
		(x, y) = (y, x % y)
	return x
MOD = 998244353

def query(a, b, c):
	print('! %d %d %d' % (a + 1, b + 1, c + 1))
	stdout.flush()
	return inp()

def my_main():
	kase = inp()
	pans = []
	for _ in range(kase):
		(n, kk) = inp()
		da = inp(True)
		da.sort()
		ans = sum(da[:n - 2 * kk])
		da = da[n - 2 * kk:]
		if da:
			ct = Counter(da)
			mxk = 0
			for (k, v) in ct.items():
				if not mxk or v > ct[mxk]:
					mxk = k
			if ct[mxk] > kk:
				ans += ct[mxk] - kk
		pans.append(str(ans))
	print('\n'.join(pans))
my_main()


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	account = 0
	a.sort(reverse=True)
	b1 = a[0:2 * k]
	b2 = a[2 * k:n]
	for i in range(k):
		account += b1[k + i] // b1[i]
	account += sum(b2)
	print(account)


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


t = int(input())
for q in range(t):
	(n, k) = [int(x) for x in input().split()]
	arr = [int(x) for x in input().split()]
	arr.sort()
	ans = 0
	(l, r) = (n - 1 - k, n - 1)
	for i in range(k):
		ans += arr[l] // arr[r]
		l -= 1
		r -= 1
	ans += sum(arr[:n - 2 * k])
	print(ans)


T = int(input())
for t in range(T):
	(n, k) = [int(i) for i in input().split()]
	A = [int(i) for i in input().split()]
	A.sort()
	taken = [0 for i in range(n)]
	right = n - 1
	left = n - 2
	ans = 0
	left = n - 2 * k
	right = left + 1
	freq = {}
	while left + k < n:
		ans += A[left] // A[left + k]
		taken[left] = 1
		taken[left + k] = 1
		left += 1
	for i in range(n):
		if taken[i] == 0:
			ans += A[i]
	print(ans)


from sys import stdin

def main():
	input = lambda : stdin.readline()[:-1]
	T = int(input())
	for _ in [0] * T:
		(N, K) = map(int, input().split())
		A = list(map(int, input().split()))
		A.sort(reverse=1)
		ax = A[K:]
		ay = A[:K]
		ans = 0
		for (i, y) in enumerate(ay):
			ans += ax[i] // y
			ax[i] = 0
		ans += sum(ax)
		print(ans)
main()


t = int(input())
for tt in range(t):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	a.sort()
	ans = 0
	for rr in range(n - 2 * k):
		ans += a[rr]
	ss = a[n - 2 * k:]
	y = []
	s = 1
	for r in range(1, 2 * k):
		if ss[r - 1] == ss[r]:
			s += 1
		else:
			y += [s]
			s = 1
	y += [s]
	y.sort()
	sum1 = 0
	for r in range(len(set(ss)) - 1):
		sum1 += y[r]
	if sum1 < y[-1]:
		ans += (y[-1] - sum1) // 2
	print(ans)


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


import sys
int1 = lambda x: int(x) - 1
pDB = lambda *x: print(*x, end='\n', file=sys.stderr)
p2D = lambda x: print(*x, sep='\n', end='\n\n', file=sys.stderr)

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

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

def LLI(rows_number):
	return [LI() for _ in range(rows_number)]

def LI1():
	return list(map(int1, sys.stdin.readline().split()))

def LLI1(rows_number):
	return [LI1() for _ in range(rows_number)]

def SI():
	return sys.stdin.readline().rstrip()
inf = 4294967295
md = 998244353

def solve():
	(n, k) = LI()
	aa = LI()
	aa.sort()
	bo = []
	si = []
	for _ in range(k):
		bo.append(aa.pop())
	for _ in range(k):
		si.append(aa.pop())
	ans = sum(aa)
	for (b, s) in zip(bo, si):
		ans += s // b
	print(ans)
for testcase in range(II()):
	solve()


from __future__ import print_function
from math import *
from collections import deque
import os
import sys
from io import BytesIO, IOBase
import heapq
from typing import Counter

def main():
	pass
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 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())
for _ in range(inp()):
	(n, k) = invr()
	l = inlt()
	l.sort(reverse=1)
	t = l[:2 * k]
	score = 0
	d = {}
	for i in range(2 * k):
		if l[i] not in d:
			d[l[i]] = 1
		else:
			d[l[i]] += 1
	x = []
	for i in d:
		x.append(-1 * d[i])
	heapq.heapify(x)
	while len(x) > 1:
		a = heapq.heappop(x)
		b = heapq.heappop(x)
		a += 1
		b += 1
		if a < 0:
			heapq.heappush(x, a)
		if b < 0:
			heapq.heappush(x, b)
	if len(x) >= 1:
		score += -1 * (x[-1] // 2)
	for i in range(2 * k, n):
		score += l[i]
	print(score)


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


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


a = int(input())
for t in range(a):
	(n, k) = map(int, input().split())
	d = input().split()
	l = [int(_) for _ in d]
	f = 0
	l.sort()
	for t in range(n - 2 * k):
		f = f + l[t]
	for t in range(n - 2 * k, n - k):
		f = f + l[t] // l[t + k]
	print(f)


from sys import stdin, stdout, setrecursionlimit
from math import gcd, sqrt, factorial, pi, inf
from collections import deque, defaultdict
from bisect import bisect, bisect_left
from time import time
from itertools import permutations as per
from heapq import heapify, heappush, heappop, heappushpop
input = stdin.readline
R = lambda : map(int, input().split())
I = lambda : int(input())
S = lambda : input().rstrip('\r\n')
L = lambda : list(R())
P = lambda x: stdout.write(str(x) + '\n')
lcm = lambda x, y: x * y // gcd(x, y)
nCr = lambda x, y: f[x] * inv(f[y] * f[x - y] % N) % N
inv = lambda x: pow(x, N - 2, N)
sumx = lambda x: (x ** 2 + x) // 2
N = 10 ** 9 + 7
for _ in range(I()):
	(n, k) = R()
	a = sorted(R())
	ans = sum(a[:n - 2 * k])
	for i in range(k):
		ans += a[n - k - i - 1] // a[-1 - i]
	print(ans)


from collections import Counter

def cal(res):
	if res:
		d = Counter(res)
		pair = d.most_common(1)[0]
		half = len(res) / 2
		if pair[1] > half:
			return pair[1] - half
		else:
			return 0
	return 0
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	arr = [int(x) for x in input().split()]
	arr.sort()
	ans = 1000000000000000
	take = 2 * k
	yessir = sum(arr)
	for i in range(take + 1):
		res = []
		res.extend(arr[:i])
		res.extend(arr[-1:-(take - i + 1):-1])
		ans = min(ans, yessir - sum(res) + cal(res))
	print(int(ans))


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	numbers = list(map(int, input().split()))
	numbers = sorted(numbers, reverse=True)
	score = 0
	cc = 0
	for i in range(k):
		score += numbers[i + k] // numbers[i]
		cc += numbers[i]
		cc += numbers[i + k]
	c = sum(numbers) - cc
	score += c
	print(score)


from math import *
from bisect import bisect_left as bl
from bisect import bisect_right as br
from collections import Counter as ctr
from collections import deque as dq
from array import array
from re import search
li = lambda : list(map(int, input().split()))
arr = lambda a: array('i', a)
bi = lambda n: bin(n).replace('0b', '')
yn = lambda f: print('NYOE S'[f::2])
sbstr = lambda a, s: search('.*'.join(a), s)

def solve():
	for _ in range(int(input())):
		(n, k) = li()
		a = li()
		a.sort()
		b = a[n - 2 * k:]
		p = 0
		for i in range(k):
			p += b[i] // b[k + i]
		print(p + sum(a[:n - 2 * k]))
solve()


t = int(input())
for i in range(t):
	(n, k) = tuple(map(int, input().split(' ')))
	a = list(map(int, input().split(' ')))
	sa = sorted(a)
	remaining = sum(sa[:n - 2 * k])
	for j in range(n - k, n):
		remaining += sa[j - k] // sa[j]
	print(remaining)


from collections import deque, Counter, defaultdict
import math
import heapq

def solve(n, k, arr):
	arr.sort()
	i = n - 2 * k
	j = i + k
	ans = 0
	while j < n:
		ans += arr[i] // arr[j]
		i += 1
		j += 1
	for x in range(n - 2 * k):
		ans += arr[x]
	return ans
T = int(input())
for _ in range(T):
	(n, k) = map(int, input().split())
	arr = list(map(int, input().split()))
	print(solve(n, k, arr))


t = int(input())
for i in range(t):
	(n, k) = list(map(int, input().split()))
	a = list(map(int, input().split()))
	a.sort()
	s = 0
	a = a[::-1]
	b = a[0:2 * k]
	ma = [0]
	j = 0
	while j < 2 * k:
		c = 1
		while j < 2 * k - 1 and b[j] == b[j + 1]:
			c += 1
			j += 1
		ma.append(c)
		j += 1
	mm = max(ma)
	s += max(mm - k, 0)
	for j in range(2 * k, n):
		s += a[j]
	print(s)


import sys
from collections import deque
input = sys.stdin.readline
for __ in range(int(input())):
	(n, k) = map(int, input().split())
	arr = list(sorted(map(int, input().split())))
	big = arr[n - k:]
	small = arr[:n - k]
	answer = small[:len(small) - len(big)]
	for (x, y) in zip(big, small[len(small) - len(big):]):
		if y == x:
			answer.append(1)
	print(sum(answer))


def solve(arr, n, k):
	arr.sort()
	s = 0
	for i in range(n - 2 * k, n - k):
		s += arr[i] // arr[i + k]
	s += sum(arr[:n - 2 * k])
	print(s)
t = int(input())
while t:
	l = [int(i) for i in input().split(' ')]
	n = l[0]
	k = l[1]
	l = [int(i) for i in input().split(' ')]
	solve(l, n, k)
	t -= 1


import math
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	l = list(map(int, input().split()))
	l = sorted(l, reverse=True)
	(score, mi) = (0, 0)
	for i in range(k):
		score += math.floor(l[k + i] / l[i])
	score += sum(l[2 * k:])
	print(score)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	a = sorted(list(map(int, input().split())), reverse=True)
	ans = 0
	for i in range(k):
		ans += a[i + k] // a[i]
	print(ans + sum(a[2 * k:]))


t = int(input())
for i in range(t):
	(n, k) = map(int, input().split())
	array = map(int, input().split())
	array = sorted(array, reverse=True)
	score = 0
	for j in range(k):
		score += array[j + k] // array[j]
	score += sum(array[2 * k:])
	print(score)


import sys
input = lambda : sys.stdin.readline().rstrip()
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	a = sorted(list(map(int, input().split())), reverse=True)
	ans = 0
	ans = sum(a[2 * k:])
	a = a[:2 * k]
	for i in range(k):
		ans += a[i + k] // a[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_list_strings():
	return list(map(str, sys.stdin.readline().strip().split()))

def solve():
	(n, k) = get_ints()
	arr = get_list()
	if k == 0:
		print(sum(arr))
		return
	arr.sort()
	ans = 0
	for i in range(n - 2 * k):
		ans += arr[i]
	final = []
	for i in range(n - 2 * k, n):
		final.append(arr[i])
	store = {}
	for ele in final:
		if ele not in store:
			store[ele] = 1
		else:
			store[ele] += 1
	req = []
	for ele in store:
		req.append(store[ele])
	req.sort()
	last = req[-1]
	length = len(req)
	temp = 2 * last - 2 * k
	if temp <= 0:
		print(ans)
		return
	ans += temp // 2
	print(ans)
T = get_int()
while T:
	solve()
	T -= 1


from sys import stdin
from collections import Counter

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

def read_ints():
	return map(int, stdin.readline().split(' '))
t = read_int()
for case_num in range(t):
	(n, k) = read_ints()
	a = list(read_ints())
	a.sort()
	ans = sum(a[:n - 2 * k])
	for i in range(n - 2 * k, n - k):
		if a[i] == a[i + k]:
			ans += 1
	print(ans)


t = int(input())
for bob in range(t):
	(n, k) = map(int, input().split())
	arr = sorted(list(map(int, input().split())), reverse=True)
	cur = sum(arr[2 * k:])
	for i in range(k):
		cur += arr[i + k] // arr[i]
	print(cur)


import sys
import bisect
import math
from collections import deque
input = lambda : sys.stdin.readline().strip()
mod = 10 ** 9 + 7

def solve():
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	a.sort(reverse=True)
	s = 0
	for i in range(k):
		s += a[i + k] // a[i]
	return s + sum(a[2 * k:])
t = 1
t = int(input())
for _ in range(t):
	print(solve())


import sys
input = lambda : sys.stdin.readline().rstrip('\r\n')
inp = lambda : list(map(int, sys.stdin.readline().rstrip('\r\n').split()))
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	a = inp()
	a.sort()
	ans = 0
	b = a[n - 2 * k:]
	t = len(b)
	i = 0
	while i < t // 2:
		ans += b[i] // b[i + k]
		i += 1
	ans += sum(a[:n - 2 * k])
	print(ans)


import sys
input = sys.stdin.readline
import math

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

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

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

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

def solveProblem(length, array, operations):
	array.sort()
	map = {}
	j = 0
	sum = 0
	for i in range(length - 2 * operations):
		sum += array[i]
	for j in range(length - 2 * operations, length):
		i = array[j]
		if i in map:
			map[i] = map[i] + 1
		else:
			map[i] = 1
	max = 0
	for item in map:
		if map[item] > max:
			max = map[item]
	if max > operations:
		sum += math.floor(max - operations)
	return sum
outp = []
x = inp()
for i in range(x):
	i1 = inlt()
	length = i1[0]
	op = i1[1]
	array = inlt()
	result = solveProblem(length, array, op)
	outp.append(result)
for out in outp:
	print(out)


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


import math
for i in range(int(input())):
	(n, k) = list(map(int, input().split()))
	l = list(map(int, input().split()))
	for a in range(n - 1):
		for j in range(n - a - 1):
			if l[j] > l[j + 1]:
				(l[j], l[j + 1]) = (l[j + 1], l[j])
	for j in range(k):
		l[-k - 1] = math.floor(l[-k - 1] / l[-1])
		l.pop(-1)
	print(sum(l))


T = int(input())
for t in range(T):
	(l_of_list, n_of_pairs) = map(int, input().split())
	numbers = list(map(int, input().split()))
	score = 0
	numbers.sort(reverse=True)
	for i in range(n_of_pairs):
		score += numbers[i + n_of_pairs] // numbers[i]
	for k in range(n_of_pairs * 2):
		numbers.remove(numbers[0])
	for j in range(len(numbers)):
		score += numbers[j]
	print(score)


from bisect import *
t = int(input())
for i in range(t):
	(n, k) = list(map(int, input().split()))
	a = list(map(int, input().split()))
	a.sort()
	ans = 0
	for x in a[0:n - 2 * k]:
		ans += x
	for (x, y) in zip(a[-2 * k:-k], a[-k:]):
		ans += x // y
	print(ans)


t = int(input())
for i in range(t):
	(n, k) = list(map(int, input().strip().split()))
	arr = list(map(int, input().strip().split()))
	if k == 0:
		print(sum(arr))
		continue
	arr.sort()
	ans = 0
	for i in range(n - 1, n - k - 1, -1):
		if arr[i] == arr[i - k]:
			ans += 1
	ans += sum(arr[:-2 * k])
	print(ans)


import math
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	l = list(map(int, input().split()))
	l.sort(reverse=True)
	c = k
	j = 0
	s = 0
	for i in range(k, n):
		if c == 0:
			break
		s += l[i] // l[j]
		(l[i], l[j]) = (0, 0)
		j += 1
		c = c - 1
	print(s + sum(l))


t = int(input())
for x in range(t):
	(n, k) = list(map(int, input().split()))
	row = input().split()
	ints = list(map(int, row))
	ints = list(reversed(sorted(ints)))
	ans = 0
	for _ in range(n - 2 * k):
		ans += ints.pop()
	ints.reverse()
	for i in range(k):
		ans += ints[i] // ints[i + k]
	print(ans)


import collections
nn = int(input())
for i in range(nn):
	(le, k) = map(int, input().split())
	lst = list(map(int, input().split()))
	lst = sorted(lst)
	x = lst[len(lst) - 2 * k:]
	ans = sum(lst[:len(lst) - 2 * k])
	x = collections.Counter(x)
	x = sorted(x.items(), key=lambda x: x[1], reverse=True)
	if len(x) == 0:
		print(ans)
	else:
		q = x[0][1]
		if q <= k:
			print(ans)
		else:
			other = 2 * k - q
			print(ans + (q - other) // 2)


import sys
import io
import math
import collections
import decimal
import itertools
import bisect
import heapq

def input():
	return sys.stdin.readline()[:-1]
INF = 10 ** 10

def solve(N, K, A):
	A.sort()
	score = sum(A[:N - 2 * K])
	if K:
		B = A[N - 2 * K:]
		counter = collections.Counter(B)
		(b, n) = counter.most_common(1)[0]
		if n > K:
			score += n - K
	return score
T0 = int(input())
for _ in range(T0):
	(N, K) = map(int, input().split())
	A = list(map(int, input().split()))
	print(solve(N, K, A))


t = int(input())
for i in range(t):
	(n, k) = map(int, input().split())
	lst = list(map(int, input().split()))
	lst.sort()
	ans = 0
	ans += sum(lst[:n - 2 * k])
	lst = lst[n - 2 * k:]
	c = 0
	start = k - 1
	end = 2 * k - 1
	while c < k:
		a = lst[start]
		b = lst[end]
		ans += a // b
		c += 1
		start -= 1
		end -= 1
	print(ans)


t = int(input())
for k in range(0, t):
	(n, k) = list(map(int, input().strip().split()))[:2]
	a = list(map(int, input().strip().split()))[:n]
	sum1 = 0
	sum2 = 0
	a1 = {}
	a.sort()
	sum1 = sum(a[0:n - 2 * k])
	a = a[n - 2 * k:]
	n = 2 * k
	for i in range(0, n):
		g = a[i]
		if a1.get(g):
			a1[g] += 1
		else:
			a1[g] = 1
	len1 = len(a)
	for (k, v) in a1.items():
		if v == 1:
			sum2 += 0
		elif v > len1 / 2:
			sum2 += int(v - len1 / 2)
	print(sum2 + sum1)


import math
t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	arr = [int(x) for x in input().split()]
	arr.sort(reverse=True)
	ans = 0
	for i in range(k):
		ans += math.floor(arr[i + k] / arr[i])
	for i in range(2 * k, n):
		ans += arr[i]
	print(ans)


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


for tt in range(int(input())):
	(n, k) = [int(i) for i in input().split()]
	a = sorted([int(i) for i in input().split()])
	print(sum(a[0:n - 2 * k]) + sum([a[i] // a[i + k] for i in range(n - 2 * k, n - k)]))


import sys, array, bisect, collections, heapq, itertools, math, functools
sys.setrecursionlimit(100000)

def _r():
	return sys.stdin.buffer.readline()

def rs():
	return _r().decode('ascii').strip()

def rn():
	return int(_r())

def rnt():
	return tuple(map(int, _r().split()))

def rnl():
	return list(rnt())

def rna():
	return array.array('q', rnt())

def pnl(l):
	print(' '.join(map(str, l)))

class MaxHeapObj:

	def __init__(self, val):
		self.val = val

	def __lt__(self, other):
		return self.val > other.val

	def __eq__(self, other):
		return self.val == other.val

	def __str__(self):
		return str(self.val)

def solve(n, k, a):
	a = sorted(a)
	sol = sum(a[:n - 2 * k])
	f = {}
	for x in a[n - 2 * k:]:
		f[x] = f.get(x, 0) + 1
	q = [MaxHeapObj(cnt) for cnt in f.values()]
	heapq.heapify(q)
	while q:
		cnt1 = heapq.heappop(q).val
		if q:
			cnt2 = heapq.heappop(q).val
			if cnt1 > 1:
				heapq.heappush(q, MaxHeapObj(cnt1 - 1))
			if cnt2 > 1:
				heapq.heappush(q, MaxHeapObj(cnt2 - 1))
		else:
			sol += 1
			if cnt1 > 2:
				heapq.heappush(q, MaxHeapObj(cnt1 - 2))
	return sol
for _ in range(rn()):
	(n, k) = rnt()
	a = rnl()
	print(solve(n, k, a))


for _ in range(int(input())):
	(n, k) = map(int, input().strip().split())
	l = list(map(int, input().strip().split()))
	l.sort(reverse=True)
	an = 0
	for i in range(k):
		if l[i] == l[i + k]:
			an += 1
	an += sum(l[2 * k:])
	print(an)


import heapq
import sys
import math
from collections import deque
from bisect import bisect_left, bisect_right
I = sys.stdin.readline
II = lambda : int(I())
IN = lambda x: map(int, x.split())
FN = lambda x: map(float, x.split())
L = lambda x: list(IN(x))
M = 1000000007
P = print
T = True
F = False
for _ in range(II()):
	(n, k) = IN(I())
	rem = n - 2 * k
	a = L(I())
	a.sort()
	sc = 0
	(f, s) = (rem, rem + k)
	for i in range(k):
		sc += a[f] // a[s]
		f += 1
		s += 1
	sc += sum(a[:rem])
	print(sc)


t = int(input())
for _ in range(t):
	(n, k) = list(map(int, input().split()))
	arr = sorted(list(map(int, input().split())))
	if k == 0:
		print(sum(arr))
		continue
	top_k = arr[-k:]
	next_top_k = arr[-2 * k:-k]
	output = sum(arr[:-2 * k])
	for i in range(len(top_k)):
		output += next_top_k[i] // top_k[i]
	print(output)


from functools import lru_cache
from heapq import heappush, heappop, heappushpop
from itertools import permutations
from operator import itemgetter, le
from collections import deque
from collections import Counter
from itertools import accumulate
from collections import defaultdict
import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
mod = 10 ** 9 + 7
inf = float('inf')

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

def LI():
	return list(map(int, sys.stdin.readline().split()))
t = I()
for _ in range(t):
	(n, k) = LI()
	a = LI()
	a.sort()
	m = n - 2 * k
	ans = sum(a[:m])
	a = a[m:]
	for i in range(k):
		x = a[i]
		y = a[i + k]
		ans += x // y
	print(ans)


from collections import Counter
T = int(input())
for _ in range(T):
	(n, k) = map(int, input().split())
	arr = [int(i) for i in input().split()]
	arr = sorted(arr)[::-1]
	if k == 0:
		print(sum(arr))
	else:
		cands = arr[:2 * k]
		ans = sum(arr[2 * k:])
		cnt = Counter(cands)
		max_freq = max(cnt.values())
		if max_freq > k:
			ans += max_freq - k
		print(ans)


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


for p in range(int(input())):
	(n, k) = map(int, input().split())
	lis = list(map(int, input().split()))
	lis.sort(reverse=True)
	a = 0
	for i in range(k):
		a += lis[i + k] // lis[i]
	print(a + sum(lis[2 * k:]))


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


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


t = int(input())
for _ in range(t):
	(n, k) = list(map(int, input().strip().split()))
	A = list(map(int, input().strip().split()))
	A.sort()
	A.reverse()
	ans = 0
	for i in range(k):
		ans += A[i + k] // A[i]
	ans += sum(A[2 * k:n])
	print(ans)


t = int(input())
for i in range(t):
	(n, k) = [int(x) for x in input().split()]
	l = [int(x) for x in input().split()]
	l.sort()
	l1 = l[0:n - k]
	l2 = l[n - k:len(l)]
	score = 0
	for j in range(k):
		score = score + l1[-1] // l2[-1]
		l1.pop()
		l2.pop()
	score = score + sum(l1)
	print(score)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	mas = sorted(list(map(int, input().split())))
	s = mas[0:n - 2 * k]
	mas2 = []
	mini = 0
	for i in range(k):
		mas2.append(mas[i + n - 2 * k] // mas[i + n - k])
	summa = sum(mas2)
	summa2 = sum(s)
	print(summa + summa2)


import sys
from math import factorial, gcd
from collections import Counter, deque, defaultdict
from bisect import bisect_left, bisect_right
from heapq import heappop, heappush, heapify, nlargest, nsmallest
from itertools import groupby
from copy import deepcopy
MOD = 10 ** 9 + 7
INF = float('inf')
input = sys.stdin.readline
rl = lambda : list(map(int, input().split()))
rs = lambda : sys.stdin.readline().strip()
for _ in range(int(input())):
	(n, k) = rl()
	A = rl()
	A.sort()
	res = 0
	for i in range(k):
		res += A[n - i - 1 - k] // A[n - i - 1]
	res += sum(A[:n - 2 * k])
	print(res)


t = int(input())
for _ in range(t):
	(n, k) = [int(i) for i in input().split(' ')]
	arr = sorted([int(i) for i in input().split(' ')])
	ans = 0
	(l, h) = (n - k - 1, n - 1)
	while k:
		ans += arr[l] // arr[h]
		l -= 1
		h -= 1
		k -= 1
	for i in range(l + 1):
		ans += arr[i]
	print(ans)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	num = sorted(list(map(int, input().split())), reverse=True)
	re = 0
	i = 0
	while i < k:
		re += num[i + k] // num[i]
		i += 1
	re += sum(num[2 * k:])
	print(re)


import math
cases = int(input())
for i in range(cases):
	(n, k) = [int(x) for x in input().split()]
	a = [int(x) for x in input().split()]
	a.sort(reverse=True)
	matching = a[:2 * k]
	rest = a[2 * k:]
	total = 0
	for i in range(k):
		total += math.floor(matching[k + i] / matching[i])
	total += sum(rest)
	print(total)


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


import math
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	arr = list(map(int, input().split()))
	arr.sort()
	a = n - 2 * k
	rem = arr[0:a]
	arr1 = arr[a:]
	rem2 = []
	for i in range(k):
		temp = arr1[i] // arr1[i + k]
		rem2.append(temp)
	rem2 += rem
	print(sum(rem2))


def func():
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	a.sort()
	ans = 0
	l = n - 1
	dif = n - k - 1
	while l >= n - k:
		ans = ans + a[dif] // a[l]
		l = l - 1
		dif = dif - 1
	l = dif
	while l >= 0:
		ans = ans + a[l]
		l = l - 1
	print(ans)
t = int(input())
for i in range(t):
	func()


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


problem_num = int(input())
for i in range(problem_num):
	(n, k) = input().split()
	n = int(n)
	k = int(k)
	arr = input().split()
	arr = [int(i) for i in arr]
	arr.sort()
	sub_main = arr[:n - 2 * k]
	sub_div = arr[n - 2 * k:]
	sub_score = 0
	for j in range(k):
		sub_score += int(sub_div[j] / sub_div[k + j])
	score = sum(sub_main) + sub_score
	print(score)


t = int(input())

def calc(arr, k):
	s = 0
	x = []
	y = []
	for i in range(k):
		x.append(arr[-1])
		arr.pop()
	for i in range(k):
		y.append(arr[-1])
		arr.pop()
	for i in range(k):
		s += y[i] // x[i]
	s += sum(arr)
	return s
for i in range(t):
	(n, k) = map(int, input().split())
	arr = sorted([int(x) for x in input().split()])
	print(calc(arr, k))


t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	liczby = list(map(int, input().split()))
	liczby.sort()
	wynik = 0
	for x in range(n - (k + k)):
		wynik += liczby[x]
	if k == 0:
		print(wynik)
	else:
		lista = []
		themost = 0
		mostoften = liczby[n - (k + k)]
		for x in range(n - (k + k), n):
			if liczby[x] == mostoften:
				themost += 1
				if x == n - 1:
					lista.append(themost)
			else:
				lista.append(themost)
				themost = 1
				mostoften = liczby[x]
				if x == n - 1:
					lista.append(themost)
		themost = max(lista)
		if themost > k:
			temp = k + k - themost
			wynik += (themost - temp) // 2
		print(wynik)


import collections
t = int(input())
for _ in range(t):
	[n, k] = [int(i) for i in input().split()]
	x = [int(i) for i in input().split()]
	x.sort(reverse=True)
	freq = collections.Counter(x[0:2 * k])
	flag = True
	sm = 0
	for (key, value) in freq.items():
		if value > k:
			sm += value - k
	sm += sum(x[2 * k:])
	print(sm)


import sys
input = sys.stdin.readline

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

def st():
	return input().rstrip('\n')

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

def ma():
	return map(int, input().split())
t = inp()
while t:
	t -= 1
	(n, k) = ma()
	a = lis()
	a.sort()
	score = 0
	extra = n - 2 * k
	score += sum(a[:extra])
	a = a[extra:]
	z = len(a) // 2
	for i in range(z):
		score += a[i] // a[i + z]
	print(score)


t = int(input())
from math import *
for p in range(t):
	(n, k) = map(int, input().split())
	lis = list(map(int, input().split()))
	lis.sort()
	sus = 0
	sussy = sum(lis)
	lis = lis[n - 2 * k:]
	for i in range(1, k + 1):
		(a, b) = (lis[k - i], lis[2 * k - i])
		sussy -= a + b
		sussy += a // b
	print(sussy)


def solve():
	(n, k) = map(int, input().split())
	arr = sorted(list(map(int, input().split())))
	score = 0
	for i in range(k):
		score += arr[n - 1 - i - k] // arr[n - i - 1]
	for i in range(n - 2 * k):
		score += arr[i]
	return score
for _ in range(int(input())):
	print(solve())


from math import floor

def solve():
	(n, k) = list(map(int, input().split()))
	arr = list(map(int, input().split()))
	arr.sort()
	l = 0
	r = n - 1
	res = 0
	for i in range(n - 2 * k, n - k):
		res += floor(arr[i] / arr[i + k])
	for i in range(n - 2 * k):
		res += arr[i]
	print(res)
t = int(input())
while t:
	t -= 1
	solve()


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


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


from math import floor
for test in range(int(input())):
	(n, k) = list(map(int, input().split()))
	arr = list(map(int, input().split()))
	arr.sort()
	ans = sum(arr[:n - 2 * k])
	for i in range(k):
		ans += floor(arr[n - 2 * k + i] / arr[n - k + i])
	print(ans)


import os
import sys
from io import BytesIO, IOBase
from types import GeneratorType
from collections import defaultdict
BUFSIZE = 8192

def bootstrap(f, stack=[]):

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

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')
import math
import heapq
t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	b = sorted(list(map(int, input().split())))
	res = b[n - 2 * k:n]
	req = b[:n - 2 * k]
	s = sum(req)
	l = len(res)
	i = 0
	d = defaultdict(lambda : 0)
	while i < l:
		d[res[i]] += 1
		i += 1
	v = []
	for j in d:
		v.append(d[j])
	v = sorted(v)
	if len(v):
		s1 = sum(v) - v[-1]
		if s1 <= v[-1]:
			v[-1] -= s1
			s += v[-1] // 2
	print(s)


import math

def main_function():
	test_cases = range(int(input()))
	for test_case in test_cases:
		(n, k) = [int(i) for i in input().split(' ')]
		a = sorted([int(i) for i in input().split(' ')], reverse=True)
		counter = 0
		what_will_be_left = n - 2 * k
		current_ind = -1
		for i in range(what_will_be_left):
			counter += a[-1]
			a.pop()
		hash_a = {}
		for i in a:
			if i in hash_a:
				hash_a[i] += 1
			else:
				hash_a[i] = 1
		for i in hash_a:
			if hash_a[i] > k:
				counter += hash_a[i] - k
		print(counter)
main_function()


t = int(input())
for _ in range(t):
	(n, k) = [int(i) for i in input().split()]
	lst = [int(i) for i in input().split()]
	lst.sort()
	if k == 0:
		print(sum(lst))
		continue
	div = lst[-k:]
	lst = lst[:-k]
	d = lst[-k:]
	lst = lst[:-k]
	cnt = sum(lst) + sum([x // y for (x, y) in zip(d, div)])
	print(cnt)


n = int(input())
for i in range(n):
	(_, k) = [int(j) for j in input().split()]
	a = [int(_) for _ in input().split()]
	a.sort()
	ans = sum(a[:len(a) - 2 * k])
	for i in range(len(a) - 2 * k, len(a) - k):
		ans += 1 if a[i] == a[i + k] else 0
	print(ans)


import math, sys
input = sys.stdin.readline
S = lambda : input().rstrip()
I = lambda : int(S())
M = lambda : map(int, S().split())
L = lambda : list(M())
mod1 = 1000000007
mod2 = 998244353
for _ in range(I()):
	(n, k) = M()
	a = sorted(L())
	ans = sum(a[:n - 2 * k])
	i = n - 2 * k
	j = n - k
	while j < n:
		ans += a[i] // a[j]
		i += 1
		j += 1
	print(ans)


import atexit, io, sys, math, heapq, collections

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

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 write_int(a):
	sys.stdout.write(str(a) + '\n')

def write_str(a):
	sys.stdout.write(a + '\n')

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

def swap(arr, a, b):
	arr[a] ^= arr[b]
	arr[b] ^= arr[a]
	arr[a] ^= arr[b]

def int_len(a):
	return math.floor(math.log(a, 10)) + 1

def isPowerOfTwo(x):
	return x and (not x & x - 1)

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

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

def search(arr, x):
	return binarySearch(arr, 0, len(arr) - 1, x)

def toString(A):
	return ''.join(A)

def toArray(str):
	return str.split()

def arrSum(Arr):
	Sum = 0
	for i in range(len(Arr)):
		Sum += Arr[i]
	return Sum

def computeXOR(n):
	if n % 4 == 0:
		return n
	if n % 4 == 1:
		return 1
	if n % 4 == 2:
		return n + 1
	return 0

def find_gcd(x, y):
	while y:
		(x, y) = (y, x % y)
	return x
N = get_int()
while N > 0:
	(n, k) = get_ints()
	Arr = get_list()
	Arr.sort()
	score = 0
	for i in range(0, k):
		score += Arr[n - 2 * k + i] // Arr[n - k + i]
	for i in range(0, n - 2 * k):
		score += Arr[i]
	print(score)
	N -= 1


import os
import sys
from bisect import bisect, bisect_left, insort, insort_left
from heapq import heapify, heappop, heappush, nlargest, nsmallest
from io import BytesIO, IOBase
from math import inf, sqrt
from types import GeneratorType
BUFSIZE: int = 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()
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))

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

def bootstrap(f, stack=[]):

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

def modInverse(a, m):
	g = gcd(a, m)
	if g != 1:
		return -1
	else:
		return power(a, m - 2, m)

def power(x, y, m):
	if y == 0:
		return 1
	p = power(x, y // 2, m) % m
	p = p * p % m
	if y % 2 == 0:
		return p
	else:
		return x * p % m

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

def SieveOfEratosthenes(n):
	prime = [True for i in range(n + 1)]
	p = 2
	while p * p <= n:
		if prime[p] == True:
			for i in range(p * p, n + 1, p):
				prime[i] = False
		p += 1
	ans = set()
	for p in range(2, n + 1):
		if prime[p]:
			ans.add(p)
	return ans
MOD = 1000000007
INT_MAX = inf
INT_MIN = -inf

def main():
	t = int(input())
	for _ in range(t):
		temp = list(map(int, input().split()))
		(n, k) = (temp[0], temp[1])
		a = list(map(int, input().split()))
		if k == 0:
			print(sum(a))
			continue
		a.sort(reverse=True)
		ans1 = 0
		c = k
		for i in range(k):
			ans1 += int(a[c + i] / a[i])
		ans1 += sum(a[k:c])
		ans1 += sum(a[c + k:])
		print(ans1)
main()


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	a = sorted(list(map(int, input().split())), reverse=True)
	res = sum([i // j for (i, j) in zip(a[k:2 * k], a[:k])])
	if n > 2 * k:
		res += sum(a[2 * k:])
	print(res)


for i in range(int(input())):
	(n, k) = map(int, input().split())
	l = list(map(int, input().split()))
	l.sort()
	l.reverse()
	i = 0
	j = k
	ans = 0
	while i < k:
		ans += l[j] // l[i]
		i += 1
		j += 1
	for m in range(2 * k, n):
		ans += l[m]
	print(ans)


for i in range(int(input())):
	(n, k) = list(map(int, input().split()))
	a = list(map(int, input().split()))
	a.sort(reverse=True)
	s = 0
	for i in range(k):
		r = int(a[k + i] / a[i])
		a[i] = 0
		a[k + i] = 0
		s += r
	print(sum(a) + s)


import sys
from bisect import bisect_left as lb
from bisect import bisect_right as rb
from collections import deque
from queue import PriorityQueue as pq
from math import gcd
input_ = lambda : sys.stdin.readline().strip('\r\n')
ii = lambda : int(input_())
il = lambda : list(map(int, input_().split()))
ilf = lambda : list(map(float, input_().split()))
lii = lambda : list(map(int, list(ip())))
ip = lambda : input_()
fi = lambda : float(input_())
ap = lambda ab, bc, cd: ab[bc].append(cd)
li = lambda : list(input_())
pr = lambda x: print(x)
prinT = lambda x: print(x)
f = lambda : sys.stdout.flush()
inv = lambda x: pow(x, mod - 2, mod)
dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]
mod = 10 ** 9 + 7
mod1 = 998244353
for _ in range(ii()):
	(n, k) = il()
	a = il()
	a.sort(reverse=True)
	ans = 0
	t = 0
	for i in range(k):
		ans += a[i + k] // a[i]
		a[i] = a[i + k] = 0
	print(ans + sum(a))


test = int(input())
for a in range(test):
	t = list(map(int, input().split()))
	(n, k) = (t[0], t[1])
	l = list(map(int, input().split()))
	l.sort()
	score = 0
	j = n - 1
	i = j - k
	while k:
		score += l[i] // l[j]
		k -= 1
		i -= 1
		j -= 1
	for h in range(i + 1):
		score += l[h]
	print(score)


import sys
input = lambda : sys.stdin.readline()[:-1]

def array_and_operations(n, k, a):
	a.sort()
	total = 0
	for i in range(k):
		total += a[-(i + k + 1)] // a[-(i + 1)]
	for i in range(n - 2 * k):
		total += a[i]
	return total
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	sys.stdout.write(f'{array_and_operations(n, k, a)}\n')


import sys

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

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

def main():
	for _ in range(int(input())):
		(n, k) = get_ints()
		ls = get_ls()
		ans = 0
		ls.sort()
		ans = sum(ls[:n - 2 * k], sum(map(lambda x: ls[x + n - 2 * k] // ls[x + n - k], range(0, k))))
		print(ans)
main()


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


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


import math
import os
import sys
from io import BytesIO, IOBase
M = 1000000007
import random
import heapq
import threading
import bisect
import time
from functools import *
from collections import *
from itertools import *
BUFSIZE = 8192
import array

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))
input = lambda : sys.stdin.readline().rstrip('\r\n')

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 inpu():
	return int(inp())

def build(a, b, st, arr, node):
	if a == b:
		st[node] = arr[a]
		return arr[a]
	mid = (a + b) // 2
	p = build(a, mid, st, arr, 2 * node + 1)
	q = build(mid + 1, b, st, arr, 2 * node + 2)
	st[node] = p + q
	return st[node]

def update(st, a, b, x, val, node):
	if x < a or x > b:
		return
	st[node] = st[node] + val
	if a != b:
		mid = (a + b) // 2
		update(st, a, mid, x, val, 2 * node + 1)
		update(st, mid + 1, b, x, val, 2 * node + 2)

def getsum(st, a, b, l, r, node):
	if l > b or r < a:
		return 0
	if l <= a and r >= b:
		return st[node]
	mid = (a + b) // 2
	return getsum(st, a, mid, l, r, 2 * node + 1) + getsum(st, mid + 1, b, l, r, 2 * node + 2)

def dfs2(curr, parent, start, end, cnt, res, d, arr):
	res[cnt[0]] = arr[curr - 1]
	start[curr] = cnt[0]
	cnt[0] += 1
	for i in d[curr]:
		if i != parent:
			dfs2(i, curr, start, end, cnt, res, d, arr)
			cnt[0] += 1
	res[cnt[0]] = arr[curr - 1]
	end[curr] = cnt[0]

def main():
	t = 1
	t = inpu()
	for _ in range(t):
		(n, k) = sep()
		arr = lis()
		arr.sort()
		ans = sum(arr[:n - 2 * k])
		p = arr[n - 2 * k:]
		c = Counter(p)
		max1 = 0
		for i in c:
			max1 = max(max1, c[i])
		res = max(0, (2 * max1 - 2 * k) // 2)
		print(ans + res)
main()


import sys
sys.setrecursionlimit(5000001)
from collections import *
from math import *
TT = int(input())
for i in range(TT):
	(n, m) = map(int, input().split())
	lst = list(map(int, input().split()))
	start = n - m
	summ = 0
	lst.sort()
	minn = 10 ** 18
	for i in range(n - 2 * m + 1):
		summ = 0
		for j in range(i):
			summ += lst[j]
		temp = start
		for j in range(i, i + m):
			summ += lst[j] // lst[temp]
			temp += 1
		for j in range(i + m, start):
			summ += lst[j]
		minn = min(minn, summ)
	print(minn)


for i in range(int(input())):
	(n, k) = map(int, input().split())
	l2 = list(map(int, input().split()))
	l2.sort(reverse=True)
	c = sum(l2[2 * k:])
	l = l2[:2 * k]
	i = 0
	c2 = 0
	while i < k:
		if l[i] == l[i + k]:
			c2 += 1
		i += 1
	print(c + c2)


def merge(arr1, arr2):
	len1 = len(arr1)
	len2 = len(arr2)
	i = 0
	j = 0
	array = []
	while i + j < len1 + len2:
		if i == len1:
			array.append(arr2[j])
			j += 1
		elif j == len2:
			array.append(arr1[i])
			i += 1
		elif arr1[i] >= arr2[j]:
			array.append(arr1[i])
			i += 1
		else:
			array.append(arr2[j])
			j += 1
	return array

def sort(array):
	len_a = len(array)
	if len_a < 2:
		return array
	arr1 = sort(array[:len_a // 2])
	arr2 = sort(array[len_a // 2:])
	array = merge(arr1, arr2)
	return array
t = int(input())
for i in range(t):
	(n, k) = map(int, input().split())
	array = list(map(int, input().split()))
	array = sort(array)
	score = 0
	for j in range(k):
		score += array[j + k] // array[j]
	score += sum(array[2 * k:])
	print(score)


from bisect import insort, bisect_right, bisect_left
from sys import stdout, stdin, setrecursionlimit
from heapq import heappush, heappop, heapify
from io import BytesIO, IOBase
from collections import *
from itertools import *
from random import *
from string import *
from queue import *
from math import *
from re import *
from os import *

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 = read(self._fd, max(fstat(self._fd).st_size, 8192))
			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 = read(self._fd, max(fstat(self._fd).st_size, 8192))
			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:
			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')
(stdin, stdout) = (IOWrapper(stdin), IOWrapper(stdout))
(graph, mod, szzz) = ({}, 10 ** 9 + 7, lambda : sorted(zzz()))

def getStr():
	return input()

def getInt():
	return int(input())

def listStr():
	return list(input())

def getStrs():
	return input().split()

def isInt(s):
	return '0' <= s[0] <= '9'

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

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

def output(answer, end='\n'):
	stdout.write(str(answer) + end)

def lcd(xnum1, xnum2):
	return xnum1 * xnum2 // gcd(xnum1, xnum2)

def getPrimes(N=10 ** 6):
	SN = int(sqrt(N))
	sieve = [i for i in range(N + 1)]
	sieve[1] = 0
	for i in sieve:
		if i > SN:
			break
		if i == 0:
			continue
		for j in range(2 * i, N + 1, i):
			sieve[j] = 0
	prime = [i for i in range(N + 1) if sieve[i] != 0]
	return prime

def primeFactor(n, prime=getPrimes()):
	lst = []
	mx = int(sqrt(n)) + 1
	for i in prime:
		if i > mx:
			break
		while n % i == 0:
			lst.append(i)
			n //= i
	if n > 1:
		lst.append(n)
	return lst
dx = [-1, 1, 0, 0, 1, -1, 1, -1]
dy = [0, 0, 1, -1, 1, -1, -1, 1]
daysInMounth = [31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31]
num = getInt()
for i in range(num):
	(n, k) = zzz()
	arr = szzz()[::-1]
	rem = n - 2 * k
	ans = 0
	for i in range(rem):
		ans += arr.pop()
	for i in range(len(arr) // 2):
		ans += arr[k + i] // arr[i]
	if len(arr) % 2:
		ans += arr[len(arr) // 2]
	print(ans)


def op():
	(n, k) = map(int, input().split())
	a = [int(i) for i in input().split()]
	b = []
	a.sort()
	for i in range(n - 2 * k, n):
		b.append(a[i])
	m = 0
	for i in b:
		o = b.count(i)
		if o > m:
			m = o
	score = 0
	if m > k:
		score += m - k
	for i in range(n - 2 * k):
		score += a[i]
	print(score)
for i in range(int(input())):
	op()


xx = int(input())

def solve():
	arr.sort()
	b = n - 2 * k
	ans = sum(arr[:b])
	for i in range(n - k, n):
		if arr[i] == arr[i - k]:
			ans += 1
	return ans
for jj in range(xx):
	(n, k) = [int(i) for i in input().split(' ')]
	arr = [int(i) for i in input().split(' ')]
	print(solve())


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


t = int(input())
for i in range(0, t):
	(n, k) = map(int, input().split())
	L = list(map(int, input().split()))
	L.sort()
	used = [False] * n
	pref = [0] * n
	if k == 0:
		s = 0
		for u in range(0, n):
			s += L[u]
		print(s)
	else:
		s = 0
		for u in range(0, n - 2 * k):
			s += L[u]
		for v in range(n - 2 * k, n - k):
			if L[v] < L[v + k]:
				s += 0
			else:
				s += 1
		print(s)


import sys, os, io
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
import math
import bisect
t = int(input())
for a0 in range(t):
	(n, k) = [int(i) for i in input().split()]
	l = [int(i) for i in input().split()]
	l.sort()
	sc = sum(l[0:n - 2 * k])
	i = n - 1 - k
	j = n - 1
	c = k
	while c > 0:
		sc += l[i] // l[j]
		i -= 1
		j -= 1
		c -= 1
	print(sc)


from collections import defaultdict, Counter, deque
from math import sqrt, log10, log, floor, factorial, gcd
from bisect import bisect_left, bisect_right, insort
from itertools import permutations, combinations
import sys, io, os
input = sys.stdin.readline
inf = float('inf')
mod = 10 ** 9 + 7

def yn(a):
	print('YES' if a else 'NO')
ceil = lambda a, b: (a + b - 1) // b
t = int(input())
for i in range(t):
	(n, k) = [int(i) for i in input().split()]
	l = [int(i) for i in input().split()]
	l.sort()
	m1 = [l.pop() for i in range(k)]
	m2 = [l.pop() for i in range(k)]
	suma = sum(l)
	sum2 = 0
	for (i, j) in zip(m1, m2):
		sum2 += j // i
	print(suma + sum2)


from math import gcd, inf

def sol():
	(n, k) = [int(x) for x in input().split()]
	arr = [int(x) for x in input().split()]
	arr.sort()
	c = k
	ind = n - 1
	nowe = []
	ans = 0
	while c:
		nowe.append(arr[ind])
		ind -= 1
		c -= 1
	stare = []
	while ind + 1:
		stare.append(arr[ind])
		ind -= 1
	stare.reverse()
	nowe.reverse()
	while k:
		ans += int(stare[-1] / nowe[-1])
		del stare[-1]
		del nowe[-1]
		k -= 1
	ans += sum(stare)
	print(ans)

def main():
	for i in range(int(input())):
		sol()
main()


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


import math

def main():
	t = int(input())
	while t > 0:
		(n, k) = map(int, input().split())
		arr = list(map(int, input().split()))
		arr.sort()
		s = 0
		for i in range(k):
			e1 = arr[n - i - 1]
			e2 = arr[n - k - i - 1]
			s += math.floor(e2 / e1)
		for i in range(n - 2 * k):
			s += arr[i]
		print(s)
		t -= 1
main()


from sys import stdin
from collections import defaultdict

def solve():
	for _ in range(int(stdin.readline().rstrip())):
		(n, k) = map(int, stdin.readline().rstrip().split())
		A = sorted(list(map(int, stdin.readline().rstrip().split())))
		ans = sum(A[:n - 2 * k])
		freq = defaultdict(int)
		for x in A[n - 2 * k:]:
			freq[x] += 1
		for x in freq.values():
			if x > k:
				ans += x - k
		print(ans)
solve()


cases = int(input())
for c in range(cases):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	a.sort(reverse=True)
	ans = 0
	for i in range(k):
		ans += int(a[i + k] / a[i])
	for i in range(2 * k, n):
		ans += a[i]
	print(ans)


from itertools import permutations as per
from math import factorial as fact
from difflib import SequenceMatcher
t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	a = sorted([int(i) for i in input().split()])
	ans = sum(a[:n - 2 * k])
	for i in range(n - k, n):
		ans += a[i - k] // a[i]
	print(ans)


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


import sys, collections, math, bisect, heapq, random, functools, io, os, copy
input = sys.stdin.readline
out = sys.stdout.flush

def rep():
	a = list(map(int, input().split()))
	return a

def sep():
	a = list(input().split())
	return a

class UnionFind:

	def __init__(self, x) -> None:
		self.uf = [-1] * x

	def find(self, x):
		r = x
		while self.uf[x] >= 0:
			x = self.uf[x]
		while r != x:
			(self.uf[r], r) = (x, self.uf[r])
		return x

	def union(self, x, y):
		(ux, uy) = (self.find(x), self.find(y))
		if ux == uy:
			return
		if self.uf[ux] >= self.uf[uy]:
			self.uf[uy] += self.uf[ux]
			self.uf[ux] = uy
		else:
			self.uf[ux] += self.uf[uy]
			self.uf[uy] = ux
		return

	def __print__(self):
		return self.uf

def spfa(x, g, n):
	dis = [float('inf') for i in range(n)]
	dis[x] = 0
	state = [False for i in range(n)]
	state[x] = True
	queue = collections.deque()
	queue.append(x)
	while queue:
		cur = queue.popleft()
		state[cur] = False
		for next_ in g[cur]:
			if dis[next_] > dis[cur] + 1:
				dis[next_] = dis[cur] + 1
				if state[next_] == False:
					state[next_] = True
					queue.append(next_)
	return dis

def solve():
	(n, k) = map(int, input().split())
	a = rep()
	a.sort()
	left = n - 2 * k
	ans = sum(a[:left])
	l = left
	while l < left + k:
		ans += a[l] // a[l + k]
		l += 1
	print(ans)
for i in range(int(input())):
	solve()


from collections import Counter
from math import floor
t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	s = 0
	a.sort()
	for i in range(n - 2 * k):
		s += a[i]
	for j in range(n - k, n):
		s += floor(a[j - k] / a[j])
	print(s)


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


for test 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()]
	arr.sort(reverse=True)
	ans = 0
	for i in range(k):
		ans += arr[i + k] // arr[i]
	print(ans + sum(arr[2 * k:]))


import array
import bisect
import heapq
import math
import collections
import sys
import copy
from functools import reduce
import decimal
from io import BytesIO, IOBase
import os
import itertools
import functools
from types import GeneratorType
decimal.getcontext().rounding = decimal.ROUND_HALF_UP
graphDict = collections.defaultdict
queue = collections.deque

def bootstrap(f, stack=[]):

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

class Graphs:

	def __init__(self):
		self.graph = graphDict(set)

	def add_edge(self, u, v):
		self.graph[u].add(v)
		self.graph[v].add(u)

	def dfs_utility(self, nodes, visited_nodes, colors, parity, level):
		global count
		if nodes == 1:
			colors[nodes] = -1
		elif len(self.graph[nodes]) == 1 and parity % 2 == 0:
			if q == 1:
				colors[nodes] = 1
			else:
				colors[nodes] = -1
				count += 1
		elif parity % 2 == 0:
			colors[nodes] = -1
		else:
			colors[nodes] = 1
		visited_nodes.add(nodes)
		for neighbour in self.graph[nodes]:
			new_level = level + 1
			if neighbour not in visited_nodes:
				self.dfs_utility(neighbour, visited_nodes, colors, level - 1, new_level)

	def dfs(self, node):
		Visited = set()
		color = collections.defaultdict()
		self.dfs_utility(node, Visited, color, 0, 0)
		return color

	def bfs(self, node, f_node):
		count = float('inf')
		visited = set()
		level = 0
		if node not in visited:
			queue.append([node, level])
			visited.add(node)
		flag = 0
		while queue:
			parent = queue.popleft()
			if parent[0] == f_node:
				flag = 1
				count = min(count, parent[1])
			level = parent[1] + 1
			for item in self.graph[parent[0]]:
				if item not in visited:
					queue.append([item, level])
					visited.add(item)
		return count if flag else -1
		return False

class Tree:

	def __init__(self, data):
		self.data = data
		self.left = None
		self.right = None

def inorder(node, lis):
	if node:
		inorder(node.left, lis)
		lis.append(node.data)
		inorder(node.right, lis)
	return lis

def leaf_node_sum(root):
	if root is None:
		return 0
	if root.left is None and root.right is None:
		return root.data
	return leaf_node_sum(root.left) + leaf_node_sum(root.right)

def hight(root):
	if root is None:
		return -1
	if root.left is None and root.right is None:
		return 0
	return max(hight(root.left), hight(root.right)) + 1

class UnionFind:
	parents = []
	sizes = []
	count = 0

	def __init__(self, n):
		self.count = n
		self.parents = [i for i in range(n)]
		self.sizes = [1 for i in range(n)]

	def find(self, i):
		if self.parents[i] == i:
			return i
		else:
			self.parents[i] = self.find(self.parents[i])
			return self.parents[i]

	def unite(self, i, j):
		root_i = self.find(i)
		root_j = self.find(j)
		if root_i == root_j:
			return
		elif root_i < root_j:
			self.parents[root_j] = root_i
			self.sizes[root_i] += self.sizes[root_j]
		else:
			self.parents[root_i] = root_j
			self.sizes[root_j] += self.sizes[root_i]

	def same(self, i, j):
		return self.find(i) == self.find(j)

	def size(self, i):
		return self.sizes[self.find(i)]

	def group_count(self):
		return len(set((self.find(i) for i in range(self.count))))

	def answer(self, extra, p, q):
		dic = collections.Counter()
		for q in range(n):
			dic[self.find(q)] = self.size(q)
		hq = list(dic.values())
		heapq._heapify_max(hq)
		ans = -1
		for z in range(extra + 1):
			if hq:
				ans += heapq._heappop_max(hq)
			else:
				break
		return ans

def rounding(n):
	return int(decimal.Decimal(f'{n}').to_integral_value())

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 p_sum(array):
	return list(itertools.accumulate(array))

def base_change(nn, bb):
	if nn == 0:
		return [0]
	digits = []
	while nn:
		digits.append(int(nn % bb))
		nn //= bb
	return digits[::-1]

def diophantine(a: int, b: int, c: int):
	(d, x, y) = extended_gcd(a, b)
	r = c // d
	return (r * x, r * y)

@bootstrap
def extended_gcd(a: int, b: int):
	if b == 0:
		(d, x, y) = (a, 1, 0)
	else:
		(d, p, q) = (yield extended_gcd(b, a % b))
		x = q
		y = p - q * (a // b)
	yield (d, x, y)
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, **kwargs):
		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 inp():
	return sys.stdin.readline().strip()

def map_inp(v_type):
	return map(v_type, inp().split())

def list_inp(v_type):
	return list(map_inp(v_type))
for _ in range(int(inp())):
	(n, k) = map_inp(int)
	arr = list_inp(int)
	arr.sort(reverse=True)
	ans = 0
	for i in range(n - 2 * k):
		ans += arr.pop()
	arr = arr[::-1]
	for i in range(k):
		ans += arr[i] // arr[i + k]
	print(ans)


from collections import deque as de
import math
import sys
from math import sqrt as sq
from math import floor as fl
from math import ceil as ce
from sys import stdin, stdout
import time
sys.setrecursionlimit(10 ** 7)
from collections import Counter as cnt
from functools import reduce
from itertools import groupby as gb
from bisect import bisect_left as bl, bisect_right as br
from typing import Coroutine

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)))

class My_stack:

	def __init__(self):
		self.data = []

	def my_push(self, x):
		return self.data.append(x)

	def my_pop(self):
		return self.data.pop()

	def __iter__(self):
		return iter(self.data)

	def my_peak(self):
		return self.data[-1]

	def my_contains(self, x):
		return self.data.count(x)

	def my_show_all(self):
		return self.data

	def isEmpty(self):
		return len(self.data) == 0

	def len(self):
		return len(self.data)
arrStack = My_stack()

class graph:

	def __init__(self):
		self.graphdict = {}

	def add_edge(self, node, neighbor):
		if node not in self.graphdict:
			self.graphdict[node] = [neighbor]
		else:
			self.graphdict[node].append(neighbor)

	def show_edge(self):
		for node in self.graphdict:
			for neighbors in self.graphdict:
				print(node, neighbors)

	def show_graph(self):
		return self.graphdict

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

def binarytodecimal(n):
	return int(n, 2)

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

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

def get_frequency(list):
	dic = {}
	for ele in list:
		if ele in dic:
			dic[ele] += 1
		else:
			dic[ele] = 1
	return dic

def Log2(x):
	return math.log10(x) / math.log10(2)

def getProduct(n):
	product = 1
	while n != 0:
		product = product * (n % 10)
		n = n // 10
	return product

def regularBracketsequence(str, arrStack):
	for i in range(len(str)):
		if str[i] == '(':
			arrStack.my_push(str[i])
		elif arrStack.isEmpty():
			return False
		else:
			arrStack.my_pop()
	if arrStack.isEmpty():
		return True
	else:
		return False

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

def isPowerOfTwo(n):
	return math.ceil(Log2(n)) == math.floor(Log2(n))

def checkisap(list):
	d = list[1] - list[0]
	for i in range(2, len(list)):
		temp = list[i] - list[i - 1]
		if temp != d:
			return False
	return True

def primes_method5(n):
	out = {}
	sieve = [True] * (n + 1)
	for p in range(2, n + 1):
		if sieve[p]:
			out[p] = 1
			for i in range(p, n + 1, p):
				sieve[i] = False
	return out

def id(i, j, col):
	ans = (i - 1) * col
	ans += j
	return ans

def getSum(n):
	strr = str(n)
	list_of_number = list(map(int, strr.strip()))
	return sum(list_of_number)

def checkperfectsquare(n):
	if ce(sq(n)) == fl(sq(n)):
		return True
	else:
		return False

def combinatrics(n, r):
	num = n
	deno = n - r
	pr = 1
	for i in range(num, deno, -1):
		pr *= i
	an = 1
	for i in range(1, r + 1):
		an *= i
	ans = pr // an
	return ans

def ceildiv(x, y):
	return (x + y - 1) // y

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

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

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

def si():
	return list(map(str, input()))

def indict():
	dic = {}
	for (index, value) in enumerate(input().split()):
		dic[int(value)] = int(index)
	return dic

def frqdict():
	dic = {}
	for (index, value) in enumerate(input()):
		if value not in dic:
			dic[value] = 1
		else:
			dic[value] += 1
	return dic
t = ii()
while t:
	t -= 1
	(n, k) = di()
	a = sorted(li(), reverse=True)
	if k == 0:
		print(sum(a))
	else:
		score = 0
		for i in range(k):
			temp = a[i + k] // a[i]
			score += temp
		score += sum(a[2 * k:])
		print(score)


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


import math
mod = 10 ** 18 + 9

def catalan(n):
	return int(math.factorial(2 * n) // (math.factorial(n) * math.factorial(n + 1))) % mod
t = int(input())
for i in range(t):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	a.sort()
	ans = sum(a[0:n - 2 * k])
	idx1 = n - 2 * k
	idx2 = n - k
	for j in range(0, k):
		ans += a[idx1 + j] // a[idx2 + j]
	print(ans)


def sol():
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	a.sort()
	ans2 = 0
	c = n - 1
	for i in range(k):
		ans2 += a[c - 1] // a[c]
		c -= 2
	s = sum(a[:n - 2 * k])
	l = n - 2 * k
	r = n - 1
	ans = 0
	p = {}
	for i in range(l, r + 1):
		if a[i] not in p.keys():
			p[a[i]] = 1
		else:
			p[a[i]] += 1
	f = 0
	for (i, v) in p.items():
		f = max(f, v)
	print(s + max(2 * f - 2 * k, 0) // 2)
for _ in range(int(input())):
	sol()


import math
import os
import sys
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')
for _ in range(int(input())):
	(n, k) = list(map(int, input().split()))
	arr = list(map(int, input().split()))
	arr.sort()
	ans = 0
	for i in range(k):
		ans += arr[-(i + k + 1)] // arr[-(i + 1)]
	if k == 0:
		ans += sum(arr)
	ans += sum(arr[0:-(2 * k)])
	print(ans)


q = lambda : map(int, input().split())
for _ in range(int(input())):
	(n, k) = q()
	a = sorted(q())[::-1]
	print(k - sum((y < x for (x, y) in zip(a[:k], a[k:2 * k]))) + sum(a[2 * k:]))


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


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	l = sorted(map(int, input().split()))
	s = sum(l[:n - 2 * k])
	(i, j) = (n - 2 * k, n - k)
	for x in range(k):
		if l[i] == l[j]:
			s += 1
		(i, j) = (i + 1, j + 1)
	print(s)


from math import floor
t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	l = [int(x) for x in input().split()]
	l.sort()
	i = 0
	o = 0
	score2 = 0
	while o < k:
		score2 += floor(l[-k - 1 - o] / l[-1 - o])
		o += 1
	score2 += sum(l[:n - 2 * k])
	print(score2)


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

def inp():
	l = list(map(int, input().split()))
	return l
for _ in range(int(input())):
	(n, k) = inp()
	l = inp()
	l.sort(reverse=True)
	i = 0
	s = 0
	ss = l[:2 * k]
	c = Counter(ss)
	m = 0
	val = 0
	for i in c:
		if c[i] > m:
			m = c[i]
			val = i
	if 2 * m > 2 * k:
		x = m - (2 * k - m)
		s += x // 2
	s += sum(l[2 * k:])
	print(s)


for ii in range(int(input())):
	(n, k) = map(int, input().split())
	arr = sorted(list(map(int, input().split())))
	(res, i, temp) = (0, 0, n - 2 * k)
	while i < n - 2 * k:
		res += arr[i]
		i += 1
	for jj in range(0, k):
		res += arr[temp] // arr[temp + k]
		temp += 1
	print(res)


t = int(input())
for test in range(t):
	(n, k) = [int(x) for x in input().split()]
	a = [int(x) for x in input().split()]
	a.sort()
	ans = sum(a[:n - 2 * k])
	for i in range(n - 2 * k, n - k):
		ans += a[i] // a[k + i]
	print(ans)


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


import sys
input = lambda : sys.stdin.readline().rstrip()
T = int(input())
for _ in range(T):
	(N, K) = map(int, input().split())
	A = sorted([int(a) for a in input().split()])
	X = []
	for _ in range(K):
		X.append(A.pop())
	Y = []
	for _ in range(K):
		Y.append(A.pop())
	ans = 0
	for i in range(K):
		ans += Y[i] // X[i]
	ans += sum(A)
	print(ans)


for _ in range(int(input())):
	(n, k) = (int(i) for i in input().split())
	array = sorted((int(i) for i in input().split()), reverse=True)
	score = 0
	index = 0
	for _ in range(k):
		if index <= n - 2:
			score += array[index + k] // array[index]
			index += 1
		else:
			break
	print(score + sum(array[index + k:]))


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	arr = sorted(list(map(int, input().split())))
	ans = 0
	i = n - k - 1
	j = n - 1
	while k:
		if arr[i] == arr[j]:
			ans += 1
		arr[i] = -1
		arr[j] = -1
		i -= 1
		j -= 1
		k -= 1
	for i in range(n):
		if arr[i] != -1:
			ans += arr[i]
	print(ans)