题目描述

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

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

输入格式

第 1 行 1 个整数 n。 接下来的 n 行，每行给出一个人的过桥时间(整数，单位:秒)。 每个人的过桥时间不超过 100 秒。

输出格式

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

样例

输入#1

4
1
2
5
10

输出#1

17

解释#1

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

数据范围/约定

时间空间限制：1s, 256MB.

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

题目来源

课课通 P398-1