SP17660 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.

First line: The number of testcases **C**. Next **C** lines: The number of people in the group **N**, followed by ****N**** sorted integers **A $ _{i} $** . **A $ _{i} $** is the crossing time of the i-th person. 0 ≤ **C** ≤ 100; 1 ≤ **N** ≤ 1000; 0 ≤ **A $ _{i} $** ≤ 1000.

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