有n(0＜n＜=1000)个人需要过河，但河上只有一条小船，该船每次最多只允许两人乘坐，每人都有不同的划船速度。如果乘坐两人过河时，船速由慢者决定。问n人过河最短需要多少时间。注：船必须有人驾驶才能过河。

第一行为m,表示有m组测试数据。每组测试数据包括两行，第一行为需要过河的人数n，第二行为n个整数，分别表示每人划船的过河所需的时间。

对每组数据输出一行，表示过河所需的最短时间。