题目描述

小青要赶 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，表示需要过河的小马数量。

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

输出格式

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

输入样例 1

2
1 2

输出样例 1

2

输入样例 2

3
1 2 3

输出样例 2

6

输入样例 3

4
1 2 3 4

输出样例 3

11

数据范围

• $2\le N\le 100$。
• 每匹小马的过河时间 $t_i$ 满足 $1\le t_i\le 100$。

（2≤N≤100）