Minimum Crossing Time

You are given a group of n friends who need to cross a river at night. They have one flashlight and a single boat that can carry at most two people at a time. Each friend has a different speed, and when two friends cross together, they must move at the slower friend’s pace. The goal is to determine the minimum total time required for all friends to cross the river.

Let the time taken by each friend be denoted by \(t_1, t_2, \ldots, t_n\) where \(t_1 \leq t_2 \leq \ldots \leq t_n\). One optimal strategy is to repeatedly send the two fastest to shuttle the flashlight and the two slowest across. Specifically, when there are more than three people waiting, one should compare the two strategies below and choose the one with less time cost:

• Strategy 1: \(t_1 + 2t_2 + t_n\)
• Strategy 2: \(2t_1 + t_{n-1} + t_n\)

When the number of people left is three or fewer, a simple greedy strategy will finish the crossing optimally.

Your task is to implement a program that computes the minimum total crossing time given the number of friends and their respective crossing times.

inputFormat

The input is provided via stdin and has the following format:

T
n_1
t_11 t_12 ... t_1n1
n_2
t_21 t_22 ... t_2n2
... 
n_T
t_T1 t_T2 ... t_TnT

Here, T is the number of test cases. For each test case, the first line contains an integer n (the number of friends), and the second line contains n space-separated integers representing the time each friend requires to cross the river.

outputFormat

For each test case, output the minimum total crossing time on a new line. The output should be written to stdout.

## sample

5
3
1 2 5
4
1 2 5 10
5
1 2 5 10 15
4
1 3 6 8
4
1 10 2 5

8
17
28
18
17

</p>