“假舟楫者，非能水也，而绝江河。”这句话说的是，借助渡船的人，不是会游水，却能横渡江河。
会游水的人反而不一定能顺利地横渡江河。由于江面风浪很大，他们必须潜泳渡河。这就必须用到氧气瓶。氧气瓶当然是出题人买的，而出题人没钱，所以只买了一个。这种氧气瓶有两个输出氧气的管道，最多可供两个人同时过河；其中的氧气是无限的。
显然每次应该有两个人过河，再派对岸的一个人把氧气瓶送回来。需要注意的是，已经横渡到对岸的所有队员都可以送回氧气瓶。
现在给定你每个人渡河所需的时间，要你求出，按照以上方案把所有人送到对岸，所需的最短时间。两个人一起过河的时候，所需的时间等于慢的人所用时间。
【输入文件】第一行，一个正整数n。
其余n个正整数，在第2行，相邻两个整数之间用一个空格隔开。
【输出文件】一行1个整数，表示所用的最短时间。
【样例输入】

3
1 3 4

【样例输出】

8

【数据规模和约定】
* 对于20%的数据，n<=10
* 对于100%的数据，文件中的所有整数<=1000