Bridge Crossing

n people want to cross a bridge at night. At most two people may cross at a time, and every crossing group must carry a flashlight. There is only one flashlight among the n people, so after a group crosses, someone must carry the flashlight back so that the remaining people can cross.

Each person may cross at a different speed. When two people cross together, the group takes as long as the slower of the two. Determine the minimum total time needed for all n people to cross the bridge.

The first line contains the number of people n. Each of the next n lines contains one crossing time.

There are at most 1000 people, and no one takes more than 100 seconds to cross the bridge.

Print a single integer: the minimum number of seconds required for all n people to cross the bridge.