过河问题

题目描述

有 $n$ 个人要渡河，但只有一条小船，这条小船一次只能坐下最多两个人，并且只有一副船桨。

每个人划船的速度不一样，如果两个人一起上船，由于重量变大，划船的速度基本上相当于是划船速度最慢的那个人速度。

假设给出每个人单独划船过河所花费的时间，请问所有人都过河的总时间最短是多少？

输入格式

输入两行。

第一行是一个整数 $n$，表示要过河的人数。

第二行是 $n$ 个整数，按速度从快到慢排序好，表示每个人划船过河的时间。

输出格式

输出一行，给出所有人过河所花费的最短时间。

数据范围

$1 \le n$，$T_i \le 10^5$。

输入输出样例

输入 #1

3
1 2 3

输出 #1

6

输入 #2

4
1 2 5 10

输出 #2

17