[AGC020C] Median Sum

给定由 $n$ 个正整数 $a _ {1, 2, \cdots, n}$ 组成的可重集合，请求出它的非空子集的和的中位数。

[problemUrl]: https://atcoder.jp/contests/agc020/tasks/agc020_c $ N $ 個の整数 $ A_1 $, $ A_2 $, ..., $ A_N $ が与えられます。 $ A $ のすべての空でない部分列について、それぞれの和を考えます。このような和は $ 2^N\ -\ 1 $ 個存在し、この個数は奇数です。 これらの和を昇順に並べたものを $ S_1 $, $ S_2 $, ..., $ S_{2^N\ -\ 1} $ とします。 これらの中央値、$ S_{2^{N-1}} $ を求めてください。

入力は標準入力から以下の形式で与えられる。 > $ N $ $ A_1 $ $ A_2 $ $ ... $ $ A_N $

$ A $ のすべての空でない部分列の和を書き並べてソートした際の中央値を出力せよ。

3
1 2 1

2

1
58

58

### 制約 - $ 1\ \leq\ N\ \leq\ 2000 $ - $ 1\ \leq\ A_i\ \leq\ 2000 $ - 入力値はすべて整数である。 ### Sample Explanation 1 この場合、$ S\ =\ (1,\ 1,\ 2,\ 2,\ 3,\ 3,\ 4) $ となり、中央値は $ S_4\ =\ 2 $ です。 ### Sample Explanation 2 この場合、$ S\ =\ (58) $ となります。