题目描述

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

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

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

输入格式

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

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

输出格式

答えを出力せよ。

题目大意

题目描述

高桥君要做 $N$ 道菜， 每道菜要用 $T_i$ 的时间。

现在他有两个烤箱，每个烤箱最多烤一盘菜，求高桥君做好所有菜最少要用多少时间。

5
8 3 7 2 5

13

2
1000 1

1000

9
3 14 15 9 26 5 35 89 79

138

提示

制約

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

Sample Explanation 1

例えば $2$ つのオーブンを次のように使うことで、$13$ 分で全ての料理を作ることができます。 - $1$ つ目のオーブン：料理 $5,1$ を順に作る。 - $2$ つ目のオーブン：料理 $2,4,3$ を順に作る。