4272：过桥问题

在漆黑的夜里，$$n$$位旅行者来到了一座狭窄而且没有护栏的桥边。

如果不借助手电筒的话，大家是无论如何也不敢过桥去的。

不幸的是，$$n$$个人一共只带了一只手电筒，而桥窄得只够让两个人同时过。

如果各自单独过桥的话，$$n$$人所需要的时间已知。

而如果两人同时过桥，所需要的时间就是走得比较慢的那个人单独行动时所需的时间。

问题是，如何设计一个方案，让这$$n$$人尽快过桥。

第一行是一个正整数$$T$$表示测试案例的数量。

每组案例先是一个正整数$$n$$表示过桥的人数。

接下来一行$$n$$个正整数表示每个人过桥的时间。

保证$$T$$组案例的$$n$$之和不会超过$$200000$$。

针对每组案例，在一行中输出所有人过桥需要的总时间。

保证答案不会超过$$int$$范围。

1

4

1 2 5 10

17

$$5$$和$$10$$一起过可以更快