Description

正当恶魔猎手带领手下逃亡时，在他们面前忽然出现了一个悬崖，中间只有一条只能容两个人通过的独木桥，而这时天已经黑了，他们又只有一个火把，想过独木桥必须要火把照着才过的去。而每个人的过桥速度又不一样，两个人拿火把一起过桥的速度以速度慢的那个为准。后有追兵，前有悬崖，请你帮助恶魔猎手设计一个合理的过桥顺序，使的所有人都过到悬崖对面的总用时最少。

Input

输入由多组数据组成。
每组数据由1+n行组成：
第一行：一个整数n，表示总共与n个人要过桥，1<=n<=1000;
接下来n行，每行一个整数，表示每个人过一次桥（单程）的时间，每个数大于等于0，小于等于100。

Output

输出每组中使所有人都过到对面的最少总用时。

Sample Input

4
1
2
5
10

Sample Output

17

HINT

Source

NBU OJ