提示: 欢迎访问OurACM平台。
Problem 1495 An Old Crossing River Game

Accept: 59    Submit: 144
Time Limit: 1000 mSec    Memory Limit : 32768 KB

Problem Description

A group of N travelers has approached an old and shabby bridge and wishes to cross the river as soon as possible. However, there can be no more than two persons on the bridge at a time. Besides it's necessary to light the way with a torch for safe crossing but the group has only one torch.

Each traveler needs ti seconds to cross the river on the bridge; i=1, ... , N (ti are integers from 1 to 100). If two travelers are crossing together their crossing time is the time of the slowest traveler.

The task is to determine minimal crossing time for the whole group.

Input

The first line of the input contains a single integer T (1 <= T <= 20), the number of test cases. Then T cases follow. The first line of each case contains N, and the second line contains N integers giving the time for each traveler to cross the river. Each case is preceded by a blank line. There won't be more than 1000 people and nobody takes more than 100 seconds to cross.

Output

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

Sample Input

1 4 6 7 6 5

Sample Output

29

Submit  Back  Status  Discuss