問題文

高橋君は友達とキャンプに行くことになった。

高橋君と友達は性能が同じである $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