問題文

高橋君は料理 $1$ から $N$ の $N$ 品の料理を作ろうとしています。

料理 $i$ はオーブンを連続した $T_i$ 分間使うことで作れます。$1$ つのオーブンを $2$ つ以上の料理のために同時に使うことはできません。

$2$ つのオーブンを使えるとき、$N$ 品の料理を全て作るまでに最短で何分かかりますか？　なお、オーブンを使う時間以外は無視できるものとします。

制約

• $1 \\leq N \\leq 100$
• $1 \\leq T_i \\leq 10^3$
• 入力に含まれる値は全て整数である

入力

入力は以下の形式で標準入力から与えられる。

$N$ $T_1$ $\\ldots$ $T_N$

出力

答えを出力せよ。

入力例 1

5
8 3 7 2 5

出力例 1

13

例えば $2$ つのオーブンを次のように使うことで、$13$ 分で全ての料理を作ることができます。

• $1$ つ目のオーブン：料理 $5,1$ を順に作る。
• $2$ つ目のオーブン：料理 $2,4,3$ を順に作る。

入力例 2

2
1000 1

出力例 2

1000

入力例 3

9
3 14 15 9 26 5 35 89 79

出力例 3

138