Minimum Crossing Time

A bright sunny day, Oliver and his classmates (a total of N people) set out for a trip. They reached the east bank of a river and now wish to cross over to the west bank. However, there is only a small boat on the east bank.

The boat is too small and can only carry at most two people at a time. Each person has a crossing time T. When two people cross together, the boat takes time equal to the slower person’s crossing time. Moreover, only people on the same side of the river as the boat can board it to cross to the other side.

Given the crossing times for all N people, determine the minimum total time required for everyone to cross to the opposite bank.

Note: The input guarantees that there is always a boat available on the required bank at the appropriate times as per the described constraints.

inputFormat

The input consists of two lines:

• The first line contains an integer N (1 ≤ N ≤ 10⁵), the number of people.
• The second line contains N space-separated integers, where the i-th integer represents the crossing time T_i (1 ≤ T_i ≤ 10⁹) of the i-th person.

outputFormat

Output a single integer, which is the minimum total time needed for all people to cross the river.

sample

4
1 2 5 10

17