The Bridge

In the middle of the night, a group of tourists wants to cross an old, ruined bridge. They have only one torch. The light of the torch lets at most two tourists cross the bridge at the same time. The tourists cannot cross without the torch, nor in groups larger than two — otherwise they would fall into the river. Each tourist needs a certain amount of time to cross. When two tourists cross together they move at the pace of the slower one, so their crossing takes as long as the slower tourist needs. What is the shortest time in which all of the tourists can cross the bridge?

For example, suppose the group has 4 people who need 6, 7, 10, and 15 minutes to cross. The figure below shows one way for them to cross in 44 minutes — but they can actually do it faster.

A way to cross the bridge in 44 minutes. The number inside each circle is the time (in minutes) that tourist needs to cross the bridge.

Write a program that:

• reads a description of the group of tourists from standard input,
• finds the shortest time required for everyone to cross,
• writes that time to standard output.

The first line contains a single positive integer $n$ — the number of tourists ($1 \le n \le 100000$). Each of the next $n$ lines contains one integer: the number on the $i$-th of these lines is the time needed by the $i$-th tourist to cross the bridge. The times form a non-decreasing sequence, each value is at most $10^9$, and their sum does not exceed $10^9$.

Print a single integer: the shortest time required for all of the tourists to cross the bridge.