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
2013-12-22 14:44:53 Thomas Dybdahl Ahle
@Apoorv: You are right. Actually solving test case 4 is a fun little problem on its own.
2013-12-22 14:15:31 Apoorv Jindal
@Thomas Remove your previous comment, its a give-away.Explaining the case does take the fun out of the problem.By the way good problem.
2013-12-22 11:17:07 Thomas Dybdahl Ahle
The result for test case 4 is correct. It can be done in 15 time units.
I recommend thinking about it for a while on paper before implementing something that just "seems intuitive".

@anurag: Your solution gives the wrong answer to some pretty small variations of the test cases...

Last edit: 2013-12-28 01:57:53
2013-12-22 06:30:46 topgun
exactly is the 4th test case wrong or something ??
2013-12-21 23:46:56 ABHISHEK
Can you explain the fourth test case?
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.