Safe Passage

A group of students slipped off campus, and now they have to get from the main gate back to their dorm without any of the patrolling teachers spotting them. They have one invisibility cloak, and it is large enough to cover only two people at a time.

The students cross from the gate to the dorm alone or in pairs under the cloak. While anyone is still at the gate, someone who already reached the dorm has to carry the cloak back. Each student has a fixed time for crossing the campus alone, and a pair under the cloak moves at the pace of the slower of the two.

Find the smallest possible time for the whole group to reach the dorm.

For example, suppose there are four students: A crosses in 1 minute, B in 2 minutes, C in 7 minutes, and D in 10 minutes. This plan gets everyone to the dorm in 17 minutes.

• A and B go to the dorm together (2 minutes)
• A carries the cloak back to the gate (1 minute)
• C and D go to the dorm together (10 minutes)
• B carries the cloak back to the gate (2 minutes)
• A and B go to the dorm together (2 minutes)

The input is a single line. The first integer is the number of students $N$, with $2 \le N \le 15$. It is followed by $N$ positive integers giving the minimum time in which each student can cross the campus alone. Times are in minutes and each one is at most $5000$. The campus is very large.

Print the minimum time it takes to move the entire group from the gate to the dorm.