WAYHOME - The Bridge to Home

Late in the night, a group of people are approaching home after an exciting adventure in the wilderness. However, as a last challenge on their long and tiresome fare, they have to cross a small bridge over a raging river.

The bridge is so narrow and slippery that the group decides only to let a maximum of two people walk on it at any given time. Also, the person or pair who is walking on the bridge, must carry the single light that the group possesses.

The group asks you to determine, given the amounts of time that each person takes to cross the bridge, the minimum total amount of time it'll take the entire group to cross. Notice that, when two people walk on the bridge at the same time, their crossing time is determined by the slower walker.

Input

First line: The number of test cases C.

Next C lines: The number of people in the group N, followed by N sorted integers Ai. Ai is the crossing time of the i-th person.

0 ≤ C ≤ 100; 1 ≤ N ≤ 1000; 0 ≤ Ai ≤ 1000.

Output

For each testcase, write the minimum total amount of time it'll take the group to pass.

Example

Input:
4
1 1
2 1 2
3 1 1 1
4 1 2 4 8

Output:
1
2
3
15

In the third test case, the people can cross the bridge in the following way:

  1. The first two people walk over the bridge, taking 1 time unit.
  2. One person walks back over the bridge, with the light, taking 1 time unit.
  3. The two people, now on the left, cross the bridge, taking 1 time unit.

 


Added by:Thomas Dybdahl Ahle
Date:2013-12-21
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64

hide comments
2016-06-02 14:10:51 rainy jain
Nice Question :)

Last edit: 2016-06-03 01:02:30
2015-06-19 07:44:52
AC at second go. Costed me a WA for not considering the intuitive case as well. I thought that it was ruled out of being suboptimal, but instead it is optimal for some cases depending upon the values of the numbers in seq.


Last edit: 2016-05-09 18:03:11
2013-12-28 06:12:07 fitcat
@Thomas: The main 2 purposes for that account are:
1. Submit the code posted in the forum to verify what the posters' claims (I submitted one verbatim and got AC). After verified, try to modify the code to get AC if it looks promising. Answer back to the posters if succeed.
2. Try to get AC for new problems like this one. If not, validate the input. New problems that are not taking from known sources are prone to errors in the input.

As a result, this account helps not to screw up my spoj stats. Happy now?

Again, why did you disqualify my second solution? Just because I registered 2 accounts?
2013-12-28 03:04:51 Thomas Dybdahl Ahle
@fitcat what is the point of such a user, other than screwing the spoj stats?
2013-12-27 11:24:33 fitcat
@Thomas: (test) is my other account (it is for testing and other purposes). That's why I disqualified the AC solution of (test).

Nonetheless, why did you disqualify my second AC solution? This one is not related to those of (test).
2013-12-27 10:19:38 Thomas Dybdahl Ahle
@fitcat: Your solution appears to be a copy of one earlier submitted by @(test). @Swarna, your solution seems to be a copy of @john dykes'.
Please both explain to me why this is so.
2013-12-27 05:23:26 fitcat
@Thomas: Please tell me why you disqualified my solution?
2013-12-24 08:13:13 Apoorv Jindal
@:D You could actually prove the optimality of the solution, the way its done in greedy approach, where the solution always stays ahead or stays at level with any other alternate path.
2013-12-23 13:12:22 :D
A very good problem. It's always very informative see a solution actually being counter-intuitive.

Again, like in most cases, you should write a brute force implementation to actually determine if your solution is correct. Brute force is not trivial here, but I would say it's required as a part of solving this problem.
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.