A - 高橋君とお肉
Editorial
/


Time Limit: 2 sec / Memory Limit: 256 MB
問題文
高橋君は友達とキャンプに行くことになった。
高橋君と友達は性能が同じである 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 行に出力せよ。出力の末尾にも改行を入れること。
入力例1
4 4 6 7 10
出力例1
14
一方の肉焼き器でお肉 1 とお肉 4 を、他方の肉焼き器でお肉 2 とお肉 3 を順に焼きます (下の図は参考図)。

入力例2
3 1 2 4
出力例2
4
一方の肉焼き器でお肉 3 を焼いている間に、他方の肉焼き器で残りすべてのお肉を焼きます。
入力例3
1 29
出力例3
29