题目描述

注：input()输入函数的括号中不允许添加任何信息

编程实现

小青要赶 N(2≤N≤100)匹小马过河，N 匹小马过河都需要一定的时间(分钟)，小青每次过河最多能赶两匹小马(骑一匹并赶一匹)，返回时需骑一匹，每次过河的时间为走的慢的小马花费的时间。请计算至少需要多长时间才能把 N 匹小马全部赶过河。 例如: N = 4，4 匹小马过河需要的时间分别为1，2，3，4(单位:分钟) 用时最少的一种过河方式: 第一次:赶1分钟和 2分钟的小马过河，然后骑1分钟的小马返回，共花费 3 分钟(过去花费 2 分钟，回来花费1分钟); 第二次:赶 3 分钟和 4分钟的小马过河，然后骑 2分钟的小马返回，共花费 6分钟(过去花费 4分钟，回来花费2分钟); 第三次:赶1分钟和 2分钟的小马过河，共花费2 分钟(过去花费2分钟);赶这4 匹小马过河一共花费 11 分钟(11=3+6+2)。

输入描述

第一行输入一个正整数 N(2≤N≤100)，表示需要过河的小马数量 第二行输入N 个正整数(1≤正整数≤100)，表示每匹小马过河需要花费的时间(分钟)，正整数之间以一个空格隔开

输出描述

输出一个整数，表示赶n 匹小马全部过河至少需要花费的时间

样例

输入样例 #1

4
1 2 3 4

输出样例 #1

11