配点 : $400$ 点

問題文

高橋君は料理 $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$

出力

答えを出力せよ。

5
8 3 7 2 5

13

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

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

2
1000 1

1000

9
3 14 15 9 26 5 35 89 79

138