4233 - 基础算法-贪心算法:过河问题

通过次数

23

提交次数

69

时间限制 : 1 秒
内存限制 : 128 MB

有N个人想要过一条河,但是他们只有一条最多载两人的船。因此必须想出一个调度船来回的方法让每个人都能过河。每个人都有自己的划船速度,且同一条船上的两个人取决于慢者的速度。你的任务就是想出一个每人都能过河的最快策略。

输入

输入的第一行是一个正整数T(1 <= T <= 20),表示测试用例的组数。下面是T组用例。每个用例的第一行是正整数N,第二行是N个正整数表示每个人的划船速度。每组用例不会超出1000个人,每个人的划船时间不会超过100秒。

输出

对于每个用例,输出所有N个人都能过河的最短时间(秒)。

样例

输入

2
3
1 3 7
4
1 2 5 10

输出

11
17