Problem Statement

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

高橋君と友達は性能が同じである $2$ 個の肉焼き器を持っており、それぞれの肉焼き器にお肉を乗せて並行して焼くことができる。一旦肉焼き器にお肉を乗せたら、お肉が焼きあがるまではその肉焼き器からお肉を取り出したり、その肉焼き器に別のお肉を乗せたりはできない。お肉が焼けたらお肉を取り出すことができる。$2$ つの肉焼き器にまたがって $1$ つのお肉を置くことはできない。また、お肉は全部で $N$ 個あり、お肉には $1$ から $N$ まで番号が付けられている。お肉 $i$ を焼くのには、どちらの肉焼き器でも時間 $t_i$ だけかかる。お肉を肉焼き器に置く動作、取り出す動作には時間がかからない。

高橋君はお肉を焼く係であり、$N$ 個すべてのお肉を焼くことになった。みんなお腹が空いているので、すべてのお肉を焼くのにかかる時間を最小化させたい。

すべてのお肉を焼くのにかかる時間の最小値を求めよ。

Input

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

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)$ であることを表す。

Output

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