A. Максимизируйте счет
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

На доске записано $$$2n$$$ целых положительных чисел. От скуки вы решили сыграть в одиночную игру с числами на доске.

Вы начинаете игру со счетом $$$0$$$. Вы увеличите свой счет, выполняя следующую операцию ровно $$$n$$$ раз:

  • Выбрать два целых числа $$$x$$$ и $$$y$$$, которые записаны на доске.
  • Прибавить $$$\min(x,y)$$$ к своему счету.
  • Стереть $$$x$$$ и $$$y$$$ с доски.

Обратите внимание, что после того, как вы выполните этот ход $$$n$$$ раз, на доске больше не будет записано ни одного числа.

Найдите максимальный итоговый счет, который вы можете получить, если оптимально выполните $$$n$$$ ходов.

Входные данные

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \leq t \leq 5000$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Первая строка каждого набора входных данных содержит одно целое число $$$n$$$ ($$$1 \leq n \leq 50$$$), означающее, что на доске написано $$$2n$$$ целых чисел.

Вторая строка каждого набора входных данных содержит $$$2n$$$ целых чисел $$$a_1,a_2,\ldots,a_{2n}$$$ ($$$1 \leq a_i \leq 10^7$$$) — числа, написанные на доске.

Выходные данные

Для каждого набора входных данных выведите максимальный итоговый счет, который вы можете получить.

Пример
Входные данные
3
1
2 3
2
1 1 2 1
3
1 1 1 1 1 1
Выходные данные
2
2
3
Примечание

В первом наборе входных данных вы можете сделать только один ход. Вы выбираете $$$x=2$$$ и $$$y=3$$$, и ваш счет будет $$$\min(x,y)=2$$$.

Во втором наборе входных данных ниже приведена последовательность ходов, которая позволяет получить итоговый счет $$$2$$$:

  • На первом ходу выберите $$$x=1$$$ и $$$y=1$$$. Затем добавьте к счету $$$\min(x,y)=1$$$. После стирания $$$x$$$ и $$$y$$$ на доске останутся целые числа $$$1$$$ и $$$2$$$.
  • На втором ходу выберите $$$x=1$$$ и $$$y=2$$$. Затем добавьте к счету $$$\min(x,y)=1$$$. После удаления $$$x$$$ и $$$y$$$ на доске больше не останется целых чисел.
Можно доказать, что получить счет больше $$$2$$$ невозможно.

В третьем наборе входных данных выполните ход трижды, каждый раз прибавляя к счету $$$1$$$.