题目描述

Steve 和其他 $n$ 个村民一起生活在一个村庄里。不幸的是，由于对祖母绿分配的争执，这些村民之间没有任何人是朋友。此外，第 $i$ 个村民初始的暴躁值为 $g_i$。

Steve 可以进行如下操作任意多次：

• 选择两个村民 $i$ 和 $j$，给他们 $\max(g_i, g_j)$ 颗祖母绿让他们分享。两人的暴躁值都会减少 $\min(g_i, g_j)$，如果他们还不是朋友，则他们会成为朋友。

Steve 希望让每个村民都能通过一系列朋友关系与其他所有村民连通。也就是说，从任意一个村民出发，都可以通过朋友关系链到达任意其他村民。由于他不想让村庄的经济膨胀太多，请你计算他至少需要送出多少颗祖母绿才能实现目标。

输入格式

每组测试数据包含多个测试用例。第一行包含一个整数 $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$。

输出格式

对于每个测试用例，输出一个整数，表示 Steve 至少需要送出的祖母绿数量。

说明/提示

在第一个测试用例中，唯一的有效操作是 $i = 1$，$j = 2$。Steve 给他们 $\max(1, 2) = 2$ 颗祖母绿，他们成为朋友。

在第二个测试用例中，一种最优的操作顺序如下：

• Steve 选择 $i = 1$，$j = 3$。他给这两位村民 $\max(2, 5) = 5$ 颗祖母绿，两人的暴躁值都减少 $\min(2, 5) = 2$。此时所有人的暴躁值变为 $[0, 1, 3, 2]$；
• Steve 选择 $i = 2$，$j = 4$。他给这两位村民 $\max(1, 2) = 2$ 颗祖母绿，两人的暴躁值都减少 $\min(1, 2) = 1$。此时所有人的暴躁值变为 $[0, 0, 3, 1]$；
• Steve 选择 $i = 1$，$j = 2$。他给这两位村民 $\max(0, 0) = 0$ 颗祖母绿，两人的暴躁值都减少 $\min(0, 0) = 0$。此时所有人的暴躁值变为 $[0, 0, 3, 1]$。

此时，村民对 $(1, 3)$、$(2, 4)$ 和 $(1, 2)$ 直接成为朋友，其他所有村民之间都可以通过朋友链连通。可以证明，Steve 至少需要送出 $7$ 颗祖母绿才能实现目标。

由 ChatGPT 4.1 翻译

样例

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