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