史蒂夫和 $$$n$$$ 其他村民住在一个村庄里。不幸的是,由于祖母绿分配的争议,这些村民中没有一个与其他村民成为朋友。此外,村民 $$$i$$$ 最初有一个 脾气暴躁 $$$g_i$$$。
Steve 可以执行以下操作任意次:
- 选择两个村民 $$$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$$$。
输出
对于每个测试用例,输出一个整数 - 史蒂夫必须赠送的祖母绿的最小数量才能让每个人成为朋友。
示例
输入复制
421 242 1 5 251000000000 1000000000 1000000000 1000000000 100000000063 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$$$ 来完成此任务。