ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules

1826. Minefield

Time limit: 0.5 second
Memory limit: 64 MB
To fulfill an assignment, a reconnaissance group of n people must cross the enemy's minefield. Since the group has only one mine detector, the following course of action is taken: two agents cross the field to the enemy's side and then one agent brings the mine detector back to the remaining group. This is repeated until only two agents remain. These two agents then cross the field together.
Each person gets across the field at their own speed. The speed of a pair is determined by the speed of its slower member.
Find the minimal time the whole group needs to get over the minefield.

Input

The first line contains the integer n (2 ≤ n ≤ 100). The i-th of the following n lines specifies the time the i-th member of the group needs to get over the minefield (the time is an integer from 1 to 600).

Output

Output the minimal total time the group needs to cross the minefield.

Sample

inputoutput
4
1
10
5
2
17
Problem Author: Dmitry Teryaev
Problem Source: XII USU Open Personal Contest (March 19, 2011)