[ARC029A] 高橋君とお肉

高桥君和他的朋友一起露营。 高桥君有两个性能相同的烤肉机。这两个烤肉机可以一起工作。一旦把肉放上了烤肉机，就不能中途把肉拿下来，而且你不能同时在一个烤肉机上烤两块肉，也不能把一块烤肉放在两个烤肉机上。直到肉烤好，你才可以把肉取出来。 总共有N块肉，肉的编号为1~N，烤第i块肉所欲的时间为ti。不计算把肉放进烤肉机和拿出烤肉机的时间。 高桥君是一个肉食爱好者，他要求把所有的肉都烤完，而且因为大家的肚子都饿了，所以让烤肉的时间尽可能的最短。 请你求出烤完这些肉的最短时间。 输入输出格式： 输入： 第一行一个整数N(1≤N≤4） 接下来N行，每行是烤第i块肉的所需的时间ti(1≤ti≤50）。 输出格式： 一行，表示所需的最短的时间。

[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 $ 行に出力せよ。出力の末尾にも改行を入れること。

4
4
6
7
10

14

3
1
2
4

4

1
29

29

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