题目描述

有一群共$N$个人想要过河，但只有一艘船，且这艘船最多能载两个人。因此，必须安排某种往返运送的方案，以便划船来回，让所有人都能过河。每个人的划船速度都不同；两人一组过河时，这一组的速度由速度较慢的那个人决定。你的任务是确定一种策略，使这些人全部过河所需的时间最短。

输入

输入的第一行包含一个整数$T$（$1 \leq T \leq 20$），表示测试用例的数量。接下来是$T$个测试用例。每个测试用例的第一行包含整数$N$，第二行包含$N$个整数，分别表示每个人过河所需的时间。每个测试用例之前都有一个空行。人数不会超过$1000$人，且没有人过河所需的时间会超过$100$秒。

输出

对于每个测试用例，输出一行，包含让这$N$个人全部过河所需的总秒数。

输入数据 1

1
4
1 2 5 10

输出数据 1

17

来源

POJ 月赛 -- 2004.07.18