Background

One night, some travelers want to cross a bridge.

Problem Description

They only have one torch.

• The light from the torch allows at most two travelers to cross the bridge at the same time.
• Without the torch, or with more than $2$ people, they cannot cross.

Each traveler needs a specific amount of time to cross the bridge. When two travelers cross together, the time is counted as the slower one. Now we want to know the minimum total time needed for all travelers to cross the bridge.

Input Format

The first line contains an integer $n$, the total number of travelers.

The next $n$ lines give the crossing times of all travelers, sorted from small to large.

Output Format

Output one number, the minimum total crossing time.

4
6
7
10
15

42

Hint

For $100\%$ of the testdata, $1 \le n \le 10^5$, and each crossing time does not exceed $10^9$.

Translated by ChatGPT 5