Problem E: Lonely Adventurer

13歳の誕生日の祝いに少年Gは父親と一緒に船旅に出ていた。しかし航海の途中、不運にも船が嵐に見舞われて船が転覆してしまう。彼が目を覚ますと、そこは無人島だった。冒険家の父親の影響もあり、彼はこの状況にひるむ事なく、無人島でサバイバル生活をすることを決意した。動物を倒して肉を焼いたり、木の実を採取することで食いつなぎ、大木の下で野宿をすることでなんとか生き延びることができた。しかし、どうやら最近島の様子がおかしいようだ。動物たちは皆奇妙な行動を取るし、これは何か悪い事の予兆なのかもしれない。早くこの島から脱出せねば。

とはいえ、島からどう離れればよいのか。海の向こうには別の島が見えるが、そこまで行く方法が見当たらない。途方に暮れ、海岸沿いを歩いていたとき、ふと彼は N 隻のボートを発見した。調べてみたところ、これらはどれもうまく動くようだ。よし、このボートを使って向こうの島まで脱出しよう。ただ次の島でもまた同じようなサバイバル生活が始まるかもしれない。そのとき困らないためにも、予備として全てのボートを運んでおこう。この島で何かが起こる前に早い事済ませないと。

Problem

N 隻の各ボート i (1 ≤ i ≤ N) にはそれぞれ島Aから島Bまで(島Bから島Aまで)の移動にかかる時間 T_i (分)が与えられている。少年Gはできるだけ早く、全てのボートを初めにいる島Aから島Bに運びたいと考えている。彼がボートを運び終えるのに要する最短の時間(分)を出力せよ。ただし、ボートは一度に 2 隻まで連結して運ぶことができ、そのときにかかる時間は 2 隻のボートの内、より時間がかかるボートの時間に等しい。例えば 2 分と 4 分のボートを連結させて運ぶ場合、島Aから島Bまで（島Bから島Aまで）の移動に 4 分かかる。また 3 分のボート 2 隻を連結させて運ぶ場合は 3 分かかることになる。なお、ボートの乗り換えにかかる時間は無視してよいものとする。

Input

1行目に整数 N が与えられる。
2行目には N 個の整数 T_i が空白区切りで与えられる。

Constraints

入力は以下の条件を満たす。

• 1 ≤ N ≤ 1000
• 1 ≤ T_i ≤ 10000

Output

全てのボートを運び終えるのに要する最短の時間(分)を1行で出力せよ。

Sample Input 1

4
1 2 3 4

Sample Output 1

11

Sample Input 2

5
3 3 3 3 3

Sample Output 2

21