河流/rivers
该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。
河流/rivers
题目描述
有 个人要过河，只有一艘最多载两个人的船，第 个人独自划船过河的时间为 。
若有两个人一同过河，则花费时间为两个人的过河时间较长者。
求至少需要多少时间，才能让 个人从一侧都移动到另一侧。
输入格式
输入的第一行包含唯一一个整数 ，描述了需要过河的人数。
接下来 个整数 ，意义见上。
输出格式
输出一个整数，表示答案。
样例 #1
样例输入 #1
4
1 10 5 2
样例输出 #1
17
样例 #2
样例输入 #2
6
1 5 8 9 4 2
样例输出 #2
26
提示
样例解释
对于第一个样例：
先让第 个人与第 个人过河，耗费时间为 。
接着让第 个人独自从对岸划回来，耗费时间为 。
接着让第 个人一同过河，耗费时间为 。
接着让第 个人独自从对岸划回来，耗费时间为 。
最后第 个人与第 个人过河，耗费时间为 。
总的时间为 ，容易证明不存在更优秀的方案。
数据范围