题目描述

在马其顿王国的ohide湖里举行了一次潜水比赛。其中一个项目是从高山上跳下水，再潜水达到终点。这是一个团体项目，一支队伍由n人组成。在潜水时必须使用氧气瓶，但是每只队伍只有一个氧气瓶。最多两人同时使用一个氧气瓶，但此时两人必须同步游泳，因此两人达到终点的时间等于较慢的一个人单独游到终点所需要的时间。好在大家都很友好，因此任何两个人都愿意一起游水。安排一种潜水的策略，使得最后一名选手尽量的达到终点。

输入格式

第一行：队伍的人数n（<=1000）。

第二行：n个数，分别是n个潜水所用的时间ti(<=1000)。

输出格式

队伍到达终点的最短时间。

3
1 3 4

8

</p>

提示

输入：
6
1 6 5 2 8 9
输出：
27

来源

贪心（加2题）