# Raining

Time limit: 20 seconds

## Problem

It is an old problem:
• One day, it was raining. There were 4 people in Building A. They wanted to go to another Building B that was far away from Building A. (See the figure.)
• Some of them could walk faster and some slower, so they might require different times to walk from one building to another. In particular, the times required by them were 10 mins, 5 mins, 2 mins and 1 mins. We call the four people p10, p5, p2 and p1, respectively.
• They had only one umbrella, which could allow at most 2 people to walk together at a time. When 2 people walked together, the time required to walk from one building to another is the maximum of the times required by them. E.g., when p2 and p5 walked together with the umbrella, they required 5 mins. The umbrella could be moved from one building to another only if at least one person carried it.
• No people want to get wet. What is the shortest time for all the four people to reach Building B?
A possibe schedule is: p1 & p2 -> B (that means p1 & p2 walked to Building B, using 2 mins), p1 -> A (1 mins), p1 & p5 -> B (5 mins), p1 -> A (1 mins), p1 & p10 -> B (10 mins). The total time for this schedule is 19 mins.

Some schedule can take 17 mins. (p1 & p2 -> B, p1 -> A, p10 & p5 -> B, p2 -> A, p1 & p2 -> B).

This problem considers the situations when the number of people and their walking times are arbitrary.

## Input

The input consists of a number of test cases.
Each test case starts with a line containing a single integer 1 <= n <= 10. The next line contains n integers s1, s2, ..., sn where 1 <= si <= 1000 is the time required for the person pi to walk from one building to another when he walked alone.
The last test case starts with a line containing '0', and no further lines. Do not process this case.

## Output

For each test case, output a single line containing the minimum time for all the people to reach Building B.

```4
10 5 2 1
3
30 20 20
0
```

```17
70
```

Chan Ho Leung