测试数据来自 system/2538

作业已超过截止时间，您无法递交本题目。

时间限制：1秒　　内存限制：256M

---

【题目描述】

　　在马其顿王国的ohide湖里举行了一场潜水比赛．其中一个项目是从高山上跳下水，再潜水到达终点．这是一个团体项目，一支队伍由 \(n\) 个人组成．在潜水时必须使用氧气瓶，但是一支队伍只有一个氧气瓶．最多两个人同时使用一个氧气瓶，但此时两人必须同步游泳，因此到达终点的时间等于较慢的一个单独游到终点所需要的时间．好在大家都很友好，因此任何两个人都愿意一起游泳．安排一种潜水策略，使得最后一名选手尽早到达终点。

【输入格式】

　　第1行：一个整数 \(n\)，表示队伍的人数。
　　以下 \(n\) 行，每行一个整数，表示第 \(i\) 个人游到终点的时间 \(T_i\)。

【输出格式】

　　队伍最早到达终点的时间。

【输入输出样例1】

　Input

3
1
3
4

　Output

8

【输入输出样例2】

　Input

6
1
2
5
6
8
9

　Output

27

【数据限制】

　　对于 \(100\%\) 的数据，\(1 ≤ N ≤ 10,000\)，\(1 ≤ T_i ≤ 1,000,000,000\)。

【来源】

　　Mr.he