题目描述

在漆黑的夜里， $N$ 位旅行者来到了一座狭窄而且没有护栏的桥边。如果不借助手电筒的话，大家是无论如何也不敢过桥去的。

不幸的是， $N$ 个人一共只带了一只手电筒，而桥窄得只够让两个人同时过。

如果各自单独过桥的话， $N$ 人所需要的时间已知；而如果两人同时过桥，所需要的时间就是走得比较慢的那个人单独行动时所需的时间。

问题是，如何设计一个方案，让这 $N$ 人尽快过桥，计算成绩这 $N$ 个人的最短过桥时间。

比如：有四个人甲乙丙丁，他们过河需要的时间分别为，甲： $1$ ，乙： $2$ ，丙： $5$ ，丁： $10$ 。

第一种办法：最快的 $2$ 个人先过桥，然后让跑的最快的人来回去接剩下的人：

先让甲乙过去（ $2$ 分钟），甲回来（ $1$ 分钟），甲丙过去（ $5$ 分钟），甲回来（ $1$ 分钟），甲丁再过去（ $10$ 分钟），总共需要 $19$ 分钟就可以让四个人都过去。

第二种办法：让最慢的地 $2$ 个人一起过桥，减少最慢的人在桥上的次数。

先让甲乙过去（ $2$ 分钟），甲回来（ $1$ 分钟），丙丁过去（ $10$ 分钟），乙回来（ $2$ 分钟），甲乙再过去（ $2$ 分钟），总共需要 $17$ 分钟可以让四个人都过去。

那么最慢的时间就是需要 $17$ 分钟！

输入

每组测试数据的第一行是一个整数 $N$ ($1 \le N \le 1000$)，表示共有 $N$ 个人要过河。

每组测试数据的第二行是 $N$ 个整数 $S_i$,表示这 $N$ 个人过河所需要花时间。($0 \lt S_i \le 100$)

输出

所有人过河的最短时间。

样例

4
1 2 5 10

17

来源

贪心