题目描述
N人希望过一条河,这个河里只有一条船,一条船最多可以载两个人。每个人都有不同的划船速度;两个人的整体速度取决于较慢的那个人的速度。你的工作是确定一种策略,以最少的时间让这些人全部渡河(注意:两个人划到对岸后还需要一个人把船划回来)。
输入描述
输入的第一行包含一个整数T(1 <= T <= 20),表示接下来有T组输入。然后是T组案例。每个案例的第一行包含N,第二行包含N个整数,表示每个人过河的时间,单位为分钟。人数不会超过1000人,而且没有人需要超过100分钟才能完成渡河。
输出描述
对于每组数据,输出一行,表示N人过河所需的总分钟数。
样例输入
1
4
1 2 5 10
样例输出
17
提示