5730 - 两人过河

有n个人希望在晚上通过一座桥。在任何时刻,最多只能有两个人在桥上,并且必须要带着手电简才能通过桥。现在的麻烦是只有一个手电筒,所以必须安排某种顺序,使得手电筒可以被带回去让更多的人过桥(手电筒必须由人带回,不可以从对岸扔过去)。

每个人都有不同的过桥时间,两个人一起过桥所用的时间等于其中较慢的一个。本题的任务是找出能在最短时间内使所有人都过桥的方案。

输入

第1行1个整数n。

接下来的n行,每行给出一个人的过桥时间(整数,单位:秒)。

每个人的过桥时间不超过100秒。

输出

输出一行一个数,表示所有人过桥的最短时间。

样例

输入

4
1
2
5
10

输出

17

提示

【样例说明】

可以先让1和2过桥,然后1回来,让5和10过桥,然后2再回来带1一起过桥,时间为2+1+10+2+2=17。

【数据规模】

对于40%的数据满足:n≤100。

对于100%的数据满足:n≤1000。

来源

课课通

时间限制 1 秒
内存限制 64 MB
讨论 统计
上一题 下一题