J4 实践-2 小船过河

题目描述

一组 $N$ 个人希望只用一艘船过河，最多只能载两个人。因此，必须安排某种穿梭安排，以便来回划船，以便所有人都能穿过。每个人的划船速度不同；一对夫妇的速度由速度较慢的一对的速度决定。你的工作是确定一个策略，尽量缩短这些人的沟通时间。

输入格式

输入的第一行包含单个整数 $T$，即测试用例的数量。 然后是 $T$ 组输入。每种情况的第一行包含 $N$，第二行包含 $N$ 个整数，给出每个人过河的时间 $t_i$。每个样例前面都有一个空行。

输出格式

对于每个测试用例，打印一行，其中包含所有 $N$ 个人过河所需的总秒数。

样例输入

1
4
1 2 5 10

样例输出

17

样例分析

先让甲乙过去（ $2$ 分钟），甲回来（ $1$ 分钟），丙丁过去（ $10$ 分钟），乙回来（ $2$ 分钟），甲乙再过去（ $2$ 分钟），总共需要 $17$ 分钟就可以让四个人都过去。

数据范围

对于$100\%$ 的数据：$1 \le T \le 20$，$N \le 1000$人，$t_i \le 100$。