Start: Jul, 07, 2018 08:30:00
2018年国服院程序设计基本技能达标考核(正式)
End: Jul, 07, 2018 11:00:00
Time elapsed:
Time remaining:

你敢一个人过桥吗? 2340

Time Limit:  1 s      Memory Limit:   256 MB
Submission:324     AC:14     Score:3

Description

在漆黑的夜里,N位旅行者来到了一座狭窄而且没有护栏的桥边。如果不借助手电筒的话,大家是无论如何也不敢过桥去的。不幸的是,N个人一共只带了一只手电筒,而桥窄得只够让两个人同时过。如果各自单独过桥的话,N人所需要的时间已知;而如果两人同时过桥,所需要的时间就是走得比较慢的那个人单独行动时所需的时间。问题是,如何设计一个方案,让这N人尽快过桥。

Input

第一行是一个整数T(1<=T<=20)表示测试数据的组数
每组测试数据的第一行是一个整数N(1<=N<=1000)表示共有N个人要过桥
每组测试数据的第二行是N个整数Si,表示此人过桥所需要花时间。(0<Si<=100)

Output

For each test case, print a line containing the total number of seconds required for all the N people to cross the bridge.

Samples

input
1 4 1 5 7 12
output
26