AT_agc020_c [AGC020C] Median Sum

[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 $ のすべての空でない部分列の和を書き並べてソートした際の中央値を出力せよ。

### 制約 - $ 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) $ となります。