题目描述

小青要赶 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 匹小马全部过河至少需要花费的时间 。

4
1 2 3 4

11