B. Жители
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Стив живет в деревне с $$$n$$$ другими жителями. К сожалению, из-за споров о распределении изумрудов ни один из этих жителей не является другом другого. Более того, у жителя $$$i$$$ изначально есть недовольство $$$g_i$$$.

Стив может выполнять следующую операцию любое количество раз:

  • Выбрать двух жителей $$$i$$$ и $$$j$$$ и дать им $$$\text{max}(g_i, g_j)$$$ изумрудов для совместного использования. В таком случае у них обоих недовольство уменьшается на $$$\text{min}(g_i, g_j)$$$, и они становятся друзьями, если раньше не были.

Стив хочет сделать так, чтобы каждый житель стал другом каждому другому жителю (возможно, через некоторые промежуточные дружбы); то есть от любого жителя можно проследовать по цепочке дружб, чтобы достичь любого другого жителя. Поскольку он не хочет слишком раздувать экономику деревни, вычислите минимальное количество изумрудов, которое он должен раздать, чтобы достичь этой цели.

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

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

Первая строка каждого набора входных данных содержит одно целое число $$$n$$$ ($$$2 \le n \le 2 \cdot 10^5$$$) — количество жителей.

Вторая строка каждого набора входных данных содержит $$$n$$$ целых чисел $$$g_1, g_2,\ldots, g_n$$$ ($$$1 \le g_i \le 10^9$$$) — начальное недовольство каждого жителя.

Гарантируется, что сумма значений $$$n$$$ по всем наборам входных данных не превосходит $$$2 \cdot 10^5$$$.

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

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

Пример
Входные данные
4
2
1 2
4
2 1 5 2
5
1000000000 1000000000 1000000000 1000000000 1000000000
6
3 1 4 1 5 9
Выходные данные
2
7
3000000000
14
Примечание

В первом наборе входных данных единственной допустимой операцией является $$$i = 1$$$, $$$j = 2$$$. Стив дает им $$$\text{max}(1, 2) = 2$$$ изумруда, и они становятся друзьями.

Во втором наборе входных данных одна из оптимальных последовательностей операций выглядит следующим образом:

  • Стив выбирает $$$i = 1$$$, $$$j = 3$$$. Он дает жителям $$$\text{max}(2, 5) = 5$$$ изумрудов, и их недовольство уменьшается на $$$\text{min}(2, 5) = 2$$$. Теперь недовольство всех составляет $$$[0, 1, 3, 2]$$$;
  • Стив выбирает $$$i = 2$$$, $$$j = 4$$$. Он дает жителям $$$\text{max}(1, 2) = 2$$$ изумрудов, и их недовольство уменьшается на $$$\text{min}(1, 2) = 1$$$. Теперь недовольство всех составляет $$$[0, 0, 3, 1]$$$;
  • Стив выбирает $$$i = 1$$$, $$$j = 2$$$. Он дает жителям $$$\text{max}(0, 0) = 0$$$ изумрудов, и их недовольство уменьшается на $$$\text{min}(0, 0) = 0$$$. Теперь недовольство всех составляет $$$[0, 0, 3, 1]$$$.

После этого пары жителей $$$(1, 3)$$$, $$$(2, 4)$$$ и $$$(1, 2)$$$ становятся непосредственными друзьями, и каждая другая пара жителей связана цепочкой взаимных дружб. Можно показать, что Стив не может потратить менее $$$7$$$ изумрудов, чтобы достичь этой цели.