Bridge

Time Limit: 5 Seconds    Memory Limit: 32768 KB

A family of N people is passing a bridge at night. Since it is extremely dark, they walk with the help of a lamp. Unfortunitely the bridge is narrow, as a result a maximum of two people can cross at one time, and they must have the lamp with them. Each person walks at a different speed, and a pair must walk together at the rate of the slower person. Now here is the problem: given the size of the family (N) and the time needed for each person to cross the bridge, try to figure out the minimum total time that the family can cross the bridge.

Input

There are several test cases.

In each test case, there are 2 lines.

In the first line, an integer N will be given, which satisfies 0<=N<=100000. (Though a family of 100000 people is somewhat ridiculous.)

In the second line, N integers will be given, which are the time needed to cross the bridge for each person.

There are no extra line(s) between test cases.

Output

For each test case, output a line with one number, the minimum total time.

Sample Input

5
1 3 6 8 12

Sample Output

29

Submit

Source: ZOJ Monthly, April 2003