1001. 歪歪巧克力

题目描述

歪歪最近喜欢吃巧克力，但是巧克力比较高的价格让她头痛了。歪歪的好朋友布布发现了她不舍得买巧克力，所以布布决定为歪歪的巧克力买单。

在一天里，歪歪准备要买 $n$ 颗巧克力，第 $i$ 颗巧克力的价格是 $a_i$ 元，歪歪可以以任意的顺序选择购买这些巧克力。同时歪歪也不舍得布布为她花很多的钱，所以当一块巧克力的价格大于现在布布手里的钱的一半时，歪歪便不会让布布买这个巧克力。如果布布可以为歪歪买第 $i$ 颗巧克力，布布一定会买，所以买完之后布布的钱就会立即减少 $a_i$ 。

只要买到所有的巧克力，歪歪就会很快乐，布布想让歪歪快乐，但是布布不知道歪歪会怎么购买巧克力，所以布布至少要准备多少钱才能保证歪歪能买下所有的巧克力呢？

输入格式

第一行输入测试用例组数 $T$ 。

对于每组测试用例：

第一行，输入一个正整数 $n$ ，表示歪歪买了 $n$ 颗巧克力。

第二行，输入 $n$ 个正整数 $a_i$ ，第 $i$ 个整数表示歪歪要买价格为 $a_i$ 的巧克力。

数据保证：$T\leq20$ ，$1\leq n\leq10^{4}$ ，$a_i \leq 10^9$ 。

输出格式

输出 $T$ 行。

对于每组测试用例，每行输出一个整数，表示布布为保证歪歪能买下所有的巧克力需要至少准备的钱。

样例输入

2
5
5 4 7 9 1
4
3 77 8 2

样例输出

35
167

来源：2026杭电多校-测试专用（杭电第1场-内测） 原题链接：http://acm.hdu.edu.cn/contest/problem_show.php?cid=1237&pid=1001