Chef and Roma are playing a game. Rules of the game are quite simple.
Initially there are N piles of stones on the table.
In each turn, a player can choose one pile and remove it from the table.
Each player want to maximize the total number of stones removed by him.
Chef takes the first turn. 

Please tell Chef the maximum number of stones he can remove assuming that both players play optimally.

-----Input-----
The first line of the input contains an integer T denoting the number of test cases. The description of T test cases follows.
The first line of each test case contains a single integer N denoting the number of piles.
The second line contains N space separated integers A1, A2, ..., AN denoting the number of stones in each pile.

-----Output-----
For each test case, output a single line containg the maximum number of stones that Chef can remove.

-----Constraints-----
- 1 ≤ Ai ≤ 109
- Subtask 1 (35 points): T = 10, 1 ≤ N ≤ 1000
- Subtask 2 (65 points): T = 10, 1 ≤ N ≤ 105 

-----Example-----
Input:
2
3
1 2 3
3
1 2 1

Output:
4
3

Difficulty: MEDIUM
Tags: Sorting
Skill types: Sorting

Starter code:

Solutions:
for t in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	a.sort(reverse=True)
	chef = 0
	for i in range(n):
		if i % 2 == 0:
			chef += a[i]
	print(chef)


T = int(input())
for j in range(T):
	n = int(input())
	a = list(map(int, input().split()))
	a.sort(reverse=True)
	print(sum(a[::2]))


for i in range(int(input())):
	a = int(input())
	l = list(map(int, input().split()))
	l.sort(reverse=True)
	k = 0
	s = 0
	for i in range(a):
		if i % 2 == 0:
			s += l[i]
		else:
			k += l[i]
	print(s)


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	ans = 0
	while a:
		try:
			ans += max(a)
			a.remove(max(a))
			a.remove(max(a))
		except:
			break
	print(ans)


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


def merge(arr, low, mid, high):
	n1 = mid - low + 1
	n2 = high - mid
	arr1 = []
	arr2 = []
	for i in range(n1):
		arr1.append(arr[low + i])
	for i in range(n2):
		arr2.append(arr[mid + 1 + i])
	k = low
	i = 0
	j = 0
	while i < n1 and j < n2:
		if arr1[i] < arr2[j]:
			arr[k] = arr1[i]
			k += 1
			i += 1
		else:
			arr[k] = arr2[j]
			k += 1
			j += 1
	while i < n1:
		arr[k] = arr1[i]
		k += 1
		i += 1
	while j < n2:
		arr[k] = arr2[j]
		k += 1
		j += 1
	return

def merge_sort(arr, low, high):
	if low < high:
		mid = (low + high) // 2
		merge_sort(arr, low, mid)
		merge_sort(arr, mid + 1, high)
		merge(arr, low, mid, high)
	return
t = int(input())
for z in range(t):
	n = int(input())
	arr = [int(x) for x in input().split()]
	merge_sort(arr, 0, n - 1)
	total_sum = 0
	for i in range(n - 1, -1, -2):
		total_sum += arr[i]
	print(total_sum)


t = int(input())
for i in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	l.sort()
	l.reverse()
	s = 0
	for i in range(0, len(l), 2):
		s = s + l[i]
	print(s)


t = int(input())
for i in range(t):
	a = []
	n = int(input())
	a = list(map(int, input().split()))
	chef = []
	roma = []
	count = 0
	a.sort(reverse=True)
	for j in range(0, n, 2):
		max1 = a[j]
		chef.append(max1)
	total = sum(chef)
	print(total)


for _ in range(int(input())):
	n = int(input())
	ar = [int(x) for x in input().split()]
	ar.sort(reverse=True)
	s = 0
	for i in range(0, n, 2):
		s += ar[i]
	print(s)


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	l.sort(reverse=True)
	s = 0
	for i in range(n):
		if i == 0 or i % 2 == 0:
			s += l[i]
	print(s)


t = int(input())
for _ in range(t):
	n = int(input())
	lst = sorted(list(map(int, input().split())), reverse=True)
	s = 0
	for i in range(0, n, 2):
		s = s + lst[i]
	print(s)


t = int(input())
for i in range(t):
	ans = 0
	n = int(input())
	a = [int(x) for x in input().split()]
	lis = sorted(a, reverse=True)
	for val in range(0, len(lis), 2):
		ans = ans + lis[val]
	print(ans)


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	l.sort(reverse=True)
	print(sum(l[::2]))


for i in range(int(input())):
	n = int(input())
	list1 = list(map(int, input().split()))
	list1.sort(reverse=True)
	j = 0
	sum1 = 0
	while j < n:
		sum1 += list1[j]
		j += 2
	print(sum1)


q = int(input())
for i in range(q):
	w = int(input())
	e = str(input())
	e = e + ' '
	r = ''
	t = []
	for i in e:
		if i == ' ':
			t.append(int(r))
			r = ''
		else:
			r = r + i
	t.sort()
	y = []
	for i in range(len(t)):
		y.append(t[len(t) - (i + 1)])
	o = 0
	for i in range(len(y)):
		if i % 2 == 0:
			o = o + y[i]
	print(o)


def solve():
	for _ in range(int(input())):
		_ = int(input())
		piles = list(map(int, input().split()))
		print(sum(sorted(piles, reverse=True)[::2]))
solve()


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


for t in range(int(input())):
	s = int(input())
	e = list(map(int, input().split()))
	l = sorted(e)
	count1 = 0
	l = l[::-1]
	for i in range(len(l)):
		if i % 2 == 0:
			count1 += l[i]
	print(count1)


for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	(one, two) = (0, 0)
	arr = sorted(arr, reverse=True)
	for i in range(n):
		if i & 1:
			two += arr[i]
		else:
			one += arr[i]
	print(max(one, two))


for _ in range(int(input())):
	n = int(input())
	array = [int(i) for i in input().split()]
	array.sort()
	stones1 = sum([array[i] for i in range(0, n, 2)])
	stones2 = sum([array[i] for i in range(1, n, 2)])
	print(max(stones2, stones1))


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	l.sort()
	print(sum(l[::-1][::2]))


for _ in range(0, int(input())):
	x = int(input())
	l = list(map(int, input().split()))
	l.sort(reverse=True)
	c = 0
	for i in range(0, len(l)):
		if i % 2 == 0:
			c = c + l[i]
	print(c)


T = int(input())
ans = []
for _ in range(T):
	N = int(input())
	A = [int(i) for i in input().split()]
	A.sort(reverse=True)
	count = 0
	for i in range(0, N, 2):
		count += A[i]
	ans.append(count)
for i in ans:
	print(i)


t = int(input())
for _ in range(t):
	n = int(input())
	s = list(map(int, input().split()))
	s.sort(reverse=True)
	cnt = 0
	for i in range(0, n, 2):
		cnt += s[i]
	print(cnt)


t = int(input().strip())
for _ in range(t):
	n = int(input().strip())
	a = list(map(int, input().strip().split(' ')))
	a.sort(reverse=True)
	ans = 0
	for i in range(0, n, 2):
		ans += a[i]
	print(ans)


for _ in range(int(input())):
	n = int(input())
	l = [int(i) for i in input().split()]
	g = sorted(l, reverse=True)
	s = 0
	for r in range(0, len(l), 2):
		s += g[r]
	print(s)


for _ in range(int(input())):
	n = int(input())
	print(sum((val if i % 2 == 0 else 0 for (i, val) in enumerate(sorted(list(map(int, input().split())), reverse=True)) for k in range(1))))


import math
t = int(input())
for i in range(t):
	n = int(input())
	stones = list(map(int, input().split()))
	stones = sorted(stones, reverse=True)
	total = 0
	for j in range(len(stones)):
		if j % 2 == 0:
			total += stones[j]
	print(total)


t = int(input())
for i in range(t):
	n = int(input())
	l = sorted(map(int, input().split()), reverse=True)
	print(sum(l[::2]))


for t in range(int(input())):
	N = int(input())
	arr = list(map(int, input().split()))
	arr.sort(reverse=True)
	count = 0
	for i in range(0, len(arr), 2):
		count += arr[i]
	print(count)


t = int(input())
while t > 0:
	n = int(input())
	li = [int(x) for x in input().split()]
	li.sort(reverse=True)
	c = 0
	for i in range(n):
		if i % 2 == 0:
			c += li[i]
	print(c)
	t = t - 1


for i in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	if n < 3:
		print(max(a))
	else:
		a.sort(reverse=True)
		count = 0
		for j in range(0, n, 2):
			count += a[j]
		print(count)


a = int(input(''))
for i in range(a):
	x = int(input())
	t = [int(x) for x in input().split()]
	t.sort()
	c = 0
	if x % 2 != 0:
		for j in range(0, len(t), 2):
			c = c + t[j]
	else:
		for j in range(1, len(t), 2):
			c = c + t[j]
	print(c)


t = int(input())
while t:
	n = int(input())
	a = list(map(int, input().split()))
	c = 0
	a.sort(reverse=True)
	for i in range(0, len(a), 2):
		c += a[i]
	print(c)
	t -= 1


for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	arr = sorted(arr)
	l = arr[::-1]
	x = l[::2]
	print(sum(x))


for _ in range(int(input())):
	n = int(input())
	a = sorted(map(int, input().split()), reverse=True)
	print(sum(a[0:n:2]))


t = int(input())
for i in range(t):
	n = int(input())
	l = [int(x) for x in input().split()]
	l.sort()
	o = 0
	e = 0
	if n % 2 == 0:
		for i in range(len(l)):
			if i % 2 != 0:
				o = o + l[i]
		print(o)
	else:
		for i in range(len(l)):
			if i % 2 == 0:
				e = e + l[i]
		print(e)


for _ in range(int(input())):
	piles = int(input())
	stones = list(map(int, input().split()))
	ans = 0
	stones.sort(reverse=True)
	for n in range(0, piles, 2):
		ans += stones[n]
	print(ans)


for i in range(int(input())):
	count = 0
	n = int(input())
	a = list(map(int, input().split(' ')))
	a.sort()
	count = 0
	for j in range(len(a) - 1, -1, -2):
		count = count + a[j]
	print(count)


import math
t = int(input())
for _ in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	l.sort(reverse=True)
	p = 0
	for i in range(0, n, 2):
		p += l[i]
	print(p)


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split(' ')))
	a.sort(reverse=True)
	r = a[0:n:2]
	print(sum(r))


t = int(input())
while t > 0:
	p = int(input())
	l = list(map(int, input().split()))
	l.sort()
	l.reverse()
	sum = 0
	for i in range(0, p):
		if i % 2 == 0:
			sum += l[i]
	print(sum)
	t -= 1


for i in range(int(input())):
	k = int(input())
	l = list(map(int, input().split()))
	a = sorted(l)
	a = a[::-1]
	b = a[0:k:2]
	print(sum(b))


for t in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	l.sort(reverse=True)
	chef = 0
	for x in range(n):
		if x % 2 == 0:
			chef += l[x]
	print(chef)


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


t = int(input())
while t > 0:
	n = int(input())
	l = list(map(int, input().strip().split()))
	l.sort(reverse=True)
	maxi = 0
	for i in range(n):
		if i % 2 == 0:
			maxi += l[i]
	print(maxi)
	t -= 1


for _ in range(int(input())):
	n = int(input())
	lis = list(map(int, input().split()))
	lis.sort()
	chef = sum([lis[i] for i in range(0, n, 2)])
	other = sum((lis[i] for i in range(1, n, 2)))
	print(max(chef, other))


import math
t = int(input())
for i in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	l.sort(reverse=True)
	r = math.ceil(len(l) / 2)
	res_chef = 0
	for j in range(len(l)):
		if (j + 1) % 2 == 1:
			res_chef += l[j]
	print(res_chef)


t = int(input())
while t:
	n = int(input())
	a = [int(i) for i in input().split()]
	a.sort(reverse=True)
	print(sum(a[::2]))
	t -= 1


for _ in range(int(input())):
	n = int(input())
	lst = list(map(int, input().split()))
	lst.sort()
	print(sum(lst[::-2]))


for _ in range(int(input())):
	a = int(input())
	l = list(map(int, input().split()))
	l.sort()
	print(sum(l[::-2]))


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


for i in range(int(input())):
	noturn = int(input())
	list1 = input().split()
	list1 = sorted([int(i) for i in list1], reverse=True)
	sum1 = 0
	if noturn % 2 == 0:
		for i in range(int(noturn / 2)):
			sum1 += list1[i * 2]
	else:
		for i in range(int(noturn / 2) + 1):
			sum1 += list1[i * 2]
	print(sum1)


t = int(input())
while t:
	n = int(input())
	arr = list(map(int, input().split(' ')))
	arr.sort(reverse=True)
	chef = 0
	for i in range(0, n, 2):
		chef += arr[i]
	print(chef)
	t -= 1


t = int(input())
for _ in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	l.sort(reverse=True)
	ct = 0
	for i in range(0, n, 2):
		ct += l[i]
	print(ct)


T = int(input())
for i in range(T):
	N = int(input())
	list = [int(x) for x in map(int, input().split())]
	list.sort()
	k = N - 1
	sum = 0
	while k >= 0:
		sum = sum + list[k]
		k = k - 2
	print(sum)


from sys import stdin

def main():
	n = int(stdin.readline())
	ls = [int(x) for x in stdin.readline().split()]
	ls = sorted(ls, reverse=True)
	s = 0
	for i in range(0, n, 2):
		s += ls[i]
	print(s)

def __starting_point():
	for _ in range(int(stdin.readline())):
		main()
__starting_point()


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


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


tt = int(input())
while tt > 0:
	n = int(input())
	l = [int(x) for x in input().split()]
	l = sorted(l)
	s = 0
	for i in range(n - 1, -1, -2):
		s = s + l[i]
	print(s)
	tt = tt - 1


t = int(input())
for i in range(0, t):
	n = int(input())
	res = list(map(int, input().split()))
	count = 0
	res.sort()
	for i in range(len(res) - 1, -1, -2):
		count += res[i]
	print(count)


for i in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	l.sort(reverse=True)
	s = 0
	s1 = 0
	for i in range(n):
		if i % 2 == 0:
			s = s + l[i]
		else:
			s1 = s1 + l[i]
	print(s)


t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split(' ')))
	a.sort()
	a.reverse()
	summ = 0
	for i in range(0, n, 2):
		summ = summ + a[i]
	print(summ)


t = int(input())
for i in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	a.sort(reverse=True)
	b = a[0:n:2]
	c = sum(b)
	print(c)


t = int(input())
while t != 0:
	t = t - 1
	n = int(input())
	a = [int(i) for i in input().split()]
	a.sort()
	count = 0
	for i in range(0, n, 2):
		count += a[n - i - 1]
	print(count)


t = int(input())
while t > 0:
	n = int(input())
	l = list(map(int, input().split()))
	c = 0
	l.sort()
	l = l[::-1]
	for i in range(0, len(l)):
		if i % 2 == 0:
			c = c + l[i]
		else:
			continue
	print(c)
	t = t - 1


for _ in range(int(input())):
	n = int(input())
	A = list(map(int, input().split()))
	A.sort(reverse=True)
	ans = 0
	i = 0
	while i < n:
		ans += A[i]
		i += 2
	print(ans)


for _ in range(int(input())):
	N = int(input())
	A = input().split()
	for i in range(len(A)):
		A[i] = int(A[i])
	count = 0
	A.sort()
	for i in range(len(A) - 1, -1, -2):
		count += A[i]
	print(count)


for t in range(int(input())):
	n = int(input())
	a = sorted(list(map(int, input().split())), reverse=True)
	print(sum(a[::2]))


test_case = int(input())
while test_case:
	n = int(input())
	array = list(map(int, input().strip().split()))
	array.sort(reverse=True)
	i = 0
	s = 0
	while i < n:
		s += array[i]
		i += 2
	print(s)
	test_case -= 1


for i in range(int(input())):
	x = int(input())
	y = list(map(int, input().split()))
	y.sort()
	print(sum(y[::-2]))


for _ in range(int(input())):
	n = int(input())
	l = sorted(list(map(int, input().split())), reverse=True)
	sum = 0
	for i in range(n):
		if i == 0 or i % 2 == 0:
			sum += l[i]
	print(sum)


for i in range(int(input())):
	N = int(input())
	A = list(map(int, input().split()))
	A.sort()
	count = 0
	for x in range(len(A) - 1, -1, -2):
		count += A[x]
	print(count)


t = int(input())
for _ in range(t):
	n = int(input())
	v = list(map(int, input().split()))
	v.sort(reverse=True)
	sum = 0
	for i in range(0, n, 2):
		sum += v[i]
	print(sum)


T = int(input())
for I in range(T):
	sum = 0
	n = int(input())
	a = [int(i) for i in input().split()]
	a.sort(reverse=True)
	for i in range(n):
		if i % 2 == 0:
			sum = sum + a[i]
	print(sum)


for i in range(int(input())):
	a = int(input())
	b = list(map(int, input().split()))
	b.sort()
	b.reverse()
	sum1 = 0
	for i in range(0, a, 2):
		sum1 += b[i]
	print(sum1)


t = int(input())
for i in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	arr.sort()
	stones_chef = 0
	for j in range(1, n + 1):
		if j % 2 != 0:
			stones_chef += arr[-j]
	print(stones_chef)


import math
t = int(input())
for i in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	l.sort(reverse=True)
	ans = 0
	for i in range(0, len(l), 2):
		ans += l[i]
	print(ans)


for _ in range(int(input())):
	n = int(input())
	piles = sorted(list(map(int, input().split())))
	print(sum([piles[i] for i in range(n - 1, -1, -2)]))


import math
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	a.sort()
	t = math.ceil(n / 2)
	s = 0
	c = -1
	for _ in range(t):
		s += a[c]
		c -= 2
	print(s)


for _ in range(int(input())):
	stones = int(input())
	piles = sorted(list(map(int, input().split())))
	piles.reverse()
	collected = piles[0::2]
	print(sum(collected))


t = int(input())
for i in range(t):
	n = input()
	a = sorted(map(int, input().split()), reverse=True)
	sum = 0
	i = 0
	while i < len(a):
		sum += a[i]
		i += 2
	print(sum)


for i in range(int(input())):
	m = int(input())
	lst = list(map(int, input().split()))
	l = max(lst)
	lst.sort()
	count = 0
	for i in range(m - 1, -1, -2):
		count += lst[i]
	print(count)


tc = int(input())
for _ in range(tc):
	n = int(input())
	a = list(map(int, input().split()))
	a = sorted(a)
	chef = []
	for i in range(n - 1, -1, -2):
		chef.append(a[i])
	print(sum(chef))