Problem: You are given N integers A_1, A_2, ..., A_N.

Consider the sums of all non-empty subsequences of A. There are 2^N - 1 such sums, an odd number.

Let the list of these sums in non-decreasing order be S_1, S_2, ..., S_{2^N - 1}.

Find the median of this list, S_{2^{N-1}}.

Constraints

* 1 \leq N \leq 2000
* 1 \leq A_i \leq 2000
* All input values are integers.

Input

Input is given from Standard Input in the following format:


N
A_1 A_2 ... A_N


Output

Print the median of the sorted list of the sums of all non-empty subsequences of A.

Examples

Input

3
1 2 1


Output

2


Input

1
58


Output

58

Solution (in PYTHON3):

Solution:
N=int(input())
A=[int(x) for x in input().split()]

#1からスタートしてlistの数字だけ左にシフトして論理和を取る。
#例えば1->4を左にシフトして論理和をとると1->10000->（元の1との論理和で）10001。
#さらに例を続ける。この次に5があるとき、10001->1000100000->（同様に）1000110001。
#つまり、スタートの1を除くと、5,6,10桁目にbitが立つ状態になる。
#求めたい部分集合の合計値が作れるかどうかはn+1桁目にbitが立っているかどうかを調べればよい。
#上記例（[4,5]の操作）では5,6,10桁目にbitが立っている＝4,5,9が作れているということ。
bits=1
for b in A:
  bits|=bits<<b

#解説どおり、答えはsum(list)/2以上で作れる部分和の最小値。
#上記bitsの定義を前提にbitsをsum(list)/2桁分だけ右にシフト。
#ココで最下位bitが立っていれば、答えはsum(list)/2。
#あとは1つずつ右にシフトして（答えも+1して）調べていくだけ。
ans=sum(A)
ans=(ans+1)//2
bits >>= ans
while True:
  if bits&1:
    break
  else:
    bits>>=1
    ans+=1
print(ans)