题目描述

在马其顿王国的ohide湖里举行了一次潜水比赛。其中一个项目是从高山上跳下水，再潜水达到终点。

这是一个团体项目，一支队伍由n人组成。在潜水时必须使用氧气瓶，但是每只队伍只有一个氧气瓶。最多两人同时使用一个氧气瓶，但此时两人必须同步游泳，因此两人达到终点的时间等于较慢的一个人单独游到终点所需要的时间。

好在大家都很友好，因此任何两个人都愿意一起游水。安排一种潜水的策略，使得最后一名选手尽量早的达到终点。

输入格式

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

下面是n行，每行1个数，分别是n个潜水所用的时间ti(<=1000)。

输出格式

1个整数，表示最少用的时间。

样例

样例数据

input

3
1 3 4

output

8
{4+1+3}
氧气瓶还必须潜水送回来^-^

限制与提示

时间限制：$1 \text {s}$

空间限制：$256 \text {MB}$