Alice 有 $$$n$$$ 本书。第 $$$1$$$-st 本书包含 $$$a_1$$$ 页,$$$2$$$-nd 本书包含 $$$a_2$$$ 页,$$$\ldots$$$,第 $$$n$$$ 页包含 $$$a_n$$$ 页。爱丽丝执行以下操作:
- 她将所有的书分成两堆非空的书。因此,每本书最终都恰好位于两堆中的一堆中。
- Alice 读了一本每堆数字最大的书。
Alice非常喜欢读书。将书分成两堆,帮助她找到她可以阅读的最大总页数。
输入
每个测试由多个测试用例组成。第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 500$$$) — 测试用例的数量。测试用例的描述如下。
每个测试用例的第一行包含一个整数 $$$n$$$ ($$$2 \le n \le 100$$$) — Alice 拥有的书籍数量。
每个测试用例的第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 10^9$$$) — 每本书的页数。
输出
对于每个测试用例,输出一个整数 - Alice 可以读取的最大页数。
示例
输入 #1
5 2 1 1 4 2 3 3 1 5 2 2 3 2 2 2 10 3 3 1 2 3
输出 #1
2 4 5 13 5
注意
在第一个测试用例中,Alice 可以将书号 $$$1$$$ 放入第一堆,将书号 $$$2$$$ 放入第二堆。然后她将阅读 $$$a_1 + a_2 = 1 + 1 = 2$$$ 页。
在第二个测试用例中,Alice 可以将编号为 $$$2$$$ 和 $$$3$$$ 的书籍放入第一堆,将编号为 $$$1$$$ 和 $$$4$$$ 的书籍放入第二堆。然后她会读第一堆中数字$$$3$$$最大的书,以及第二堆中数字$$$4$$$最大的书。然后她将阅读 $$$a_3 + a_4 = 3 + 1 = 4$$$ 页。