题目描述
露营营地与营地之间隔了一条河，夜里只有一条摆渡船。船每次最多载 2 人过河，到对岸后必须有 1 人把船划回来接其他人；每次过河（或返程）的耗时由船上速度最慢的那个人决定。
给出每个人的划船耗时，请算出让所有人全部过河的最短总时间。共有 $t$ 组询问。
输入格式
第一行一个整数 $t$。 每组数据：第一行一个整数 $n$（人数）；第二行 $n$ 个整数，为每个人单程过河所需时间。
输出格式
$t$ 行，每行一个整数：该组全员过河的最短时间。
数据范围
$$1 \le t \le 20,\quad 1 \le n \le 1000,\quad \text{单人耗时} \le 10^4$$