题目描述

$N$ 个人要乘同一条船渡河。船每次可载一人或两人，不能空船往返。每个人单独划船过河有一个用时，两人同船时用时为两人中较慢者的用时。求让所有人过河的最短总时间。

输入格式

第一行一个整数 $T$，表示数据组数。每组第一行一个整数 $N$，第二行 $N$ 个整数，表示每个人的过河用时。

输出格式

每组输出一行一个整数，表示最少需要的时间。

样例

1
4
1 2 5 10

17

数据范围

$1\le T\le20$，$1\le N\le1000$，每个人的过河时间为 $1$ 至 $100$ 的整数。