现有 n 个人想坐船到河对岸，只有一艘小船，一次能乘坐两人。每个人划船的速度都不尽相同，所以每个人都有一个渡河时间 t_i，为了保证船的平衡，当船上有两个人的时候，需要他们按照慢的那个人的速度划船。
请问最少要花费多少时间，才能使所有人都过河。
输入
第一行一个整数 n \ (1 \leq n \leq 10^5).
第二行 n 个整数 t_1,t_2,...,t_n \ (1 \leq t_i \leq 10^9)
输出
一个整数，表示答案
样例
| 标准输入 复制文本 |
4 5 7 11 16 |
| 标准输出 复制文本 |
42 |
提示
首先 1,2 先到河对岸花费 7。然后 1 回来花费 5。3,4 到河对岸花费 16。2 回来花费 7。1,2 再到河对岸花费 7。7+5+16+7+7=42.