Lonely Adventurer

Boy G was on a voyage with his father to celebrate his 13th birthday. However, during the voyage, unfortunately the ship was hit by a storm and the ship capsized. When he woke up, it was an uninhabited island. Partly due to the influence of the adventurer's father, he decided to live a survival life on an uninhabited island without being afraid of this situation. I managed to survive by defeating animals, grilling meat, collecting nuts to eat, and camping under large trees. However, it seems that the island has been strange recently. All the animals behave strangely, which may be a sign of something wrong. I have to escape from this island as soon as possible.

But how do you get away from the island? I can see another island over the sea, but I can't find a way to get there. At a loss, as he was walking along the coast, he suddenly found N boats. When I looked it up, they all seemed to work. Alright, let's use this boat to escape to the other island. However, a similar survival life may begin on the next island. Let's carry all the boats as a spare so that we will not be in trouble at that time. I have to do something early before something happens on this island.

Constraints

The input satisfies the following conditions.

• 1 ≤ N ≤ 1000
• 1 ≤ Ti ≤ 10000

Input

The integer N is given on the first line. The second line is given N integers Ti, separated by blanks.

Output

Output the shortest time (minutes) required to finish carrying all the boats in one line.

Examples

Input

4 1 2 3 4

Output

11

Input

5 3 3 3 3 3

Output

21

inputFormat

input satisfies the following conditions.

• 1 ≤ N ≤ 1000
• 1 ≤ Ti ≤ 10000

Input

The integer N is given on the first line. The second line is given N integers Ti, separated by blanks.

outputFormat

Output

Output the shortest time (minutes) required to finish carrying all the boats in one line.

Examples

Input

4 1 2 3 4

Output

11

Input

5 3 3 3 3 3

Output

21

样例

4
1 2 3 4

11