P5914 [POI 2004] MOS

One night, some travelers want to cross a bridge.

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.

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 one number, the minimum total crossing time.

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