AT_arc029_1 [ARC029A] 高橋君とお肉

[problemUrl]: https://atcoder.jp/contests/arc029/tasks/arc029_1 高橋君は友達とキャンプに行くことになった。 高橋君と友達は性能が同じである $ 2 $ 個の肉焼き器を持っており、それぞれの肉焼き器にお肉を乗せて並行して焼くことができる。一旦肉焼き器にお肉を乗せたら、お肉が焼きあがるまではその肉焼き器からお肉を取り出したり、その肉焼き器に別のお肉を乗せたりはできない。お肉が焼けたらお肉を取り出すことができる。$ 2 $ つの肉焼き器にまたがって $ 1 $ つのお肉を置くことはできない。また、お肉は全部で $ N $ 個あり、お肉には $ 1 $ から $ N $ まで番号が付けられている。お肉 $ i $ を焼くのには、どちらの肉焼き器でも時間 $ t_i $ だけかかる。お肉を肉焼き器に置く動作、取り出す動作には時間がかからない。 高橋君はお肉を焼く係であり、$ N $ 個すべてのお肉を焼くことになった。みんなお腹が空いているので、すべてのお肉を焼くのにかかる時間を最小化させたい。 すべてのお肉を焼くのにかかる時間の最小値を求めよ。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ t_1 $ $ t_2 $ : $ t_N $ - $ 1 $ 行目には、お肉の個数を表す整数 $ N\ (1\ ≦\ N\ ≦\ 4) $ が与えられる。これは、お肉が $ N $ 個あることを表す。 - $ 2 $ 行目から $ N $ 行にはお肉の情報が与えられる。$ N $ 行のうち $ i $ 行目には整数 $ t_i $ が書かれており、これはお肉 $ i $ を焼くのにかかる時間が $ t_i\ (1\ ≦\ t_i\ ≦\ 50) $ であることを表す。

すべてのお肉を焼くのにかかる時間の最小値を $ 1 $ 行に出力せよ。出力の末尾にも改行を入れること。

### Sample Explanation 1 一方の肉焼き器でお肉 $ 1 $ とお肉 $ 4 $ を、他方の肉焼き器でお肉 $ 2 $ とお肉 $ 3 $ を順に焼きます (下の図は参考図)。 !\[\](/img/arc/029/1-1.png) ### Sample Explanation 2 一方の肉焼き器でお肉 $ 3 $ を焼いている間に、他方の肉焼き器で残りすべてのお肉を焼きます。