该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

【题意】

$N$ 位旅行者来到了一座狭窄而且没有护栏的桥边。桥上有人驻守，如果没有通行证的话，士兵是不准许通过桥的。 但是 $N$ 个人一共只带了一个通行证，而士兵只允许两个人同时过。

已知 $N$ 人单独过桥所需的时间；如果两人同时过桥，所需的时间就是走得比较慢的那个人的过桥时间。

设计一个方案，求让这N人都过桥的最短时间。

【输入格式】

第一行一个整数 $T$ 表示有 $T$ 组数据。每组数据描述如下：

第一行一个整数 $N \ (1 \le N \le 1000$ ；

第二行 $N$ 个整数 $a_i \ (1 \le a_i \le 1000)$，表示第 $i$ 个人单独走所需时间。

【输出格式】

一行一个整数，表示 $N$ 人都过桥的最短时间。

1
4
1 2 3 4

11

【样例解释】

第一次让速度为1和2的人一起走，让1拿回通行证。
第二次让速度为3和4的人一起走，让速度为2的人拿回通行证，最后速度1和2的人再过桥。