Problem:
 Score : 700 points    Problem Statement 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 .        Sample Input 1 3
1 2 1      Sample Output 1 2  In this case, S = (1, 1, 2, 2, 3, 3, 4) . Its median is S_4 = 2 .       Sample Input 2 1
58      Sample Output 2 58  In this case, S = (58) .

Solution (Python):
n=int(input())
A=[int(i) for i in input().split()]
dp=1

for i in range(n):
    now=A[i]
    dp=dp|(dp<<now)

for i in range((sum(A)+1)//2,sum(A)+1):
    if dp&(1<<i)>0:
        print(i)
        break

Solution (Python):
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


n = int(input())
a = list(map(int, input().split()))
a.sort()
s = sum(a)
target = s//2 if s%2==0 else s//2+1
dp = 1
for i in range(1, n+1):
    dp = dp | (dp<<a[i-1])
ans = float("inf")
for i in range(target, s+1):
    if (dp>>i&1)==1:
        ans = min(ans, i)
        break
print(ans)

Solution (Python):
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


n = int(input())
a = list(map(int, input().split()))
a.sort()
s = sum(a)
target = s//2 if s%2==0 else s//2+1
dp = 1
for i in range(1, n+1):
    dp = dp | (dp<<a[i-1])
ans = float("inf")
for i in range(target, s+1):
    if (dp>>i&1)==1:
        ans = min(ans, i)
        break
print(ans)

Solution (Python):
import sys
input = sys.stdin.readline

n = int(input())
A = tuple(map(int, input().split()))
M = sum(A)
l = -(-M//2)
dp = 1
mask = (1<<(2*M))-1
for a in A:
  dp |= (dp<<a)&mask
dp >>= l
ans = (dp&(-dp)).bit_length() - 1 + l
print(ans)

Solution (Python):
N, *A = map(int, open(0).read().split())

dp = 1
for a in A:
    dp |= (dp << a)

cur = (sum(A) + 1) // 2
while (dp >> cur) & 1 == 0:
    cur += 1

print(cur)

Solution (Python):
import sys

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

N, *A = map(int, read().split())

dp = 1
for x in A:
    dp |= dp << x

S = bin(dp)[2:][::-1]

can_make = [i for i, x in enumerate(S) if x == '1']
n = len(can_make)
x = can_make[n // 2]
print(x)

Solution (Python):
n = int(input())
a = list(map(int,input().split()))
s = sum(a)
a.sort()
b = 1
for i in a:
  b |= b<<i
  
b &= 2**(s+1)-2**((s+1)//2)
t = b&(-b)
print(t.bit_length()-1)

Solution (Python):
n = int(input())
a = list(map(int,input().split()))
s = sum(a)
a.sort()
b = 1
for i in a:
  b |= b<<i
  
b &= 2**(s+1)-2**((s-1)//2)
while True:
  t = b&(-b)
  T = t.bit_length()-1
  if (s+1)//2 <= T <= s:
    print(T)
    break
  b ^= t

Solution (Python):
n = int(input())
a = list(map(int,input().split()))
s = sum(a)
a.sort()
b = 1
for i in a:
  b |= b<<i
  
b &= 2**(s+1)-2**((s-1)//2)
while True:
  t = b&(-b)
  
  if (s+1)//2 <= t.bit_length()-1 <= s:
    print(t.bit_length()-1)
    break
  b ^= t

Solution (Python):
n = int(input())
a = list(map(int, input().split()))

sum_a = sum(a)

dp = 1
for i in range(n):
    dp |= dp << a[i]

for i in range((sum_a + 1) // 2, sum_a + 1):
    if dp & (1 << i):
        print(i)
        exit()

Solution (Python):
def examA():
    N = I()
    ans = 0
    print(ans)
    return

def examB():
    ans = 0
    print(ans)
    return

def examC():
    N = I()
    A = LI()
    dp = 1
    for i in range(N):
        dp |= dp<<A[i]
    S = (sum(A)+1)//2
    ans = -1
    for i in range(S,2*S+1):
        if dp&(1<<i)>0:
            ans = i
            break
    print(ans)
    return

def examD():
    ans = 0
    print(ans)
    return

def examE():
    ans = 0
    print(ans)
    return

def examF():
    ans = 0
    print(ans)
    return

from decimal import Decimal as dec
import sys,bisect,itertools,heapq,math,random
from copy import deepcopy
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
def I(): return int(input())
def LI(): return list(map(int,sys.stdin.readline().split()))
def DI(): return dec(input())
def LDI(): return list(map(dec,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet,_ep
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
_ep = 10**(-12)
alphabet = [chr(ord('a') + i) for i in range(26)]

sys.setrecursionlimit(10**7)

if __name__ == '__main__':
    examC()

"""
142
12 9 1445 0 1
asd dfg hj o o
aidn
"""

Solution (Python):
import sys
input = sys.stdin.readline
N = int(input())
a = list(map(int, input().split()))
sm = sum(a)
dp = 1
for i in range(N): dp |= (dp << a[i])

x = 1 << ((sm + 1) // 2)
for i in range((sm + 1) // 2 + 1):
  if dp & x:
    print((sm + 1) // 2 + i)
    break
  x <<= 1

Solution (Python):
n = int(input())
a = list(map(int, input().split()))
d = (sum(a)+1)//2
c = 1
for x in a:
  c |= c << x
c >>= d
for i in range(d+5):
  if c & (1 << i):
    print(d+i)
    break

Solution (Python):
N=int(input())
A=list(map(int,input().split()))
S=sum(A)
if S%2==1:
    check=1
    for i in range(N):
        check=check|check<<A[i]
    for i in range(S//2+1,S+1):
        if check>>i &1==1:
            print(i)
            break
else:
    check=1
    for i in range(N):
        check=check|check<<A[i]

    for i in range(S//2,S+1):
        if check>>i &1==1:
            print(i)
            break

Solution (Python):
import sys
input = sys.stdin.readline

N = int(input())
A = list(map(int, input().split()))

bit = 1
for a in A:
    bit |= (bit<<a)

S = sum(A)
for i in range((S+1)//2, S+1):
    if bit&(1<<i):
        print(i)
        break

Solution (Python):
import sys
input = sys.stdin.readline

N = int(input())
A = list(map(int, input().split()))

bit = 1
for a in A:
    bit |= (bit<<a)

S = sum(A)
for i in range((S+1)//2, S+1):
    if bit&(1<<i):
        print(i)
        break

Solution (Python):
import sys
input = sys.stdin.readline
n = int(input())
A = list(map(int, input().split()))
M = sum(A)

s = 1 << M
for a in A:
  s |= s >> a
ans = bin(s)[2+(M+1)//2:].find("1") + (M+1)//2
print(ans)

Solution (Python):
N = int(input())
A = list(map(int,input().split()))
S = sum(A)
M = (S+1)//2

dp = 1
for a in A:
    dp |= (dp<<a)
ans = M
while 1:
    if dp&(1<<ans):
        print(ans)
        exit()
    ans += 1

Solution (Python):
N = int(input())
A = [int(a) for a in input().split()]
s = 1
for a in A:
    s |= s << a

for i in range((sum(A)+1)//2, sum(A)+1):
    if s & (1<<i):
        print(i)
        break

Solution (Python):
N = int(input())
A = [int(a) for a in input().split()]
s = 1
for a in A:
    s |= s << a

ss = bin(s)
for i in range((sum(A)+1)//2, sum(A)+1):
    if ss[-i-1] == "1":
        print(i)
        break

Solution (Python):
N = int(input())
A = [int(a) for a in input().split()]
s = 1
for a in A:
    s |= s << a

ss = bin(s)
for i in range((sum(A)+1)//2, sum(A)+1):
    if ss[-i-1] == "1":
        print(i)
        break

Solution (Python):
N = int(input())
A = [int(a) for a in input().split()]
s = 1
for a in A:
    s |= s << a

for i in range((sum(A)+1)//2, sum(A)+1):
    if s & (1<<i):
        print(i)
        break

Solution (Python):

"""

連続でない部分列問題…
中央値問題でよくあるのは、その数字以上の数がいくつ出てくるかで二分探索

部分問題：N個ある数列Aから1つ以上取って総和がK以上になる取り方はいくつあるか
→普通にdpするとできるがO(N^2*A)で無理(つーかほぼ答え)

中央値と平均値の関係は？
→今回はすべてのAが1/2の確率で選ばれるので、Aの総和/2 が全てのSの平均値となる
→だからなに・・・


=======解説をみた=======

Aのすべての合計をTとすると、前半はT/2以下で、後半はT/2以上(補集合の関係から)
求めるのは後半の一番小さい数字→T/2以上で登場する最小値

boolのDPになった！
bitsetを使えばオーダーレベルの改善になる
https://w.atwiki.jp/vivid_turtle/pages/40.html
ここに書かれている例に帰着する
"""
import sys

N = int(input())

A = list(map(int,input().split()))

asum = sum(A)

now = 1

for i in range(N):

    now = (now<<A[i]) | now

for i in range((asum+1)//2 , asum+1):

    if (1<<i) & now > 0:
        print (i)
        sys.exit()

Solution (Python):
N = int(input())
*A, = map(int, input().split())
S = sum(A)
subset_sum = 1
for a in A:
    subset_sum |= subset_sum << a
ans = (S + 1) // 2
subset_sum >>= ans
while subset_sum & 1 == 0:
    subset_sum >>= 1
    ans += 1
print(ans)

Solution (Python):

n = int(input())
a = list(map(int, input().split( )))

dp = 1
for i in range(n):
    dp |= dp<<a[i]
ans = (sum(a)+1)//2
tmp = 1<<ans
for i in range(ans):
    if dp&tmp:
        print(ans)
        exit()
    ans+=1
    tmp <<=1
print(ans)

Solution (Python):
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda:sys.stdin.readline().rstrip()
def resolve():
    n=int(input())
    A=list(map(int,input().split()))
    s=sum(A)

    dp=1
    for a in A:
        dp|=(dp<<a)

    for i in range((s+1)//2,s+1):
        if((dp>>i)&1):
            print(i)
            return
resolve()

Solution (Python):
import sys
readline = sys.stdin.readline

N = int(readline())
A = list(map(int, readline().split()))
S = sum(A)
dp = 1
for a in A:
    dp |= dp<<a
dp ^= dp&((1<<(-(-S//2))) - 1)
print((-dp&dp).bit_length() - 1)

Solution (Python):
def main():
  _,a=open(0)
  *a,=map(int,a.split())
  d=1
  for i in a:d|=d<<i
  s=0--sum(a)//2
  d>>=s
  print((d&-d).bit_length()+s-1)
main()

Solution (Python):
_,a=open(0)
*a,=map(int,a.split())
d=1
for i in a:d|=d<<i
s=0--sum(a)//2
print(bin(d)[~s::-1].find('1')+s)

Solution (Python):
_,a=open(0)
*a,=map(int,a.split())
d=1
for i in a:d|=d<<i
s=0--sum(a)//2
print(bin(d)[~s::-1].find('1')+s)

Solution (Python):
import numpy as np

N = int(input())
A = list(map(int, input().split()))

exist = np.zeros(sum(A)+1, dtype=bool)
exist[0] = True
for a in A:
    exist[a:] = exist[:-a] | exist[a:]

for i in range((sum(A)+1) // 2, sum(A) + 1):
    if exist[i]:
        print(i)
        exit()

Solution (Python):
import numpy as np

N = int(input())
A = list(map(int, input().split()))

exist = np.zeros(sum(A)+1, dtype=bool)
exist[sum(A)] = True
for a in A:
    exist[:-a] |= exist[a:]

for i in range((sum(A)+1) // 2, sum(A) + 1):
    if exist[i]:
        print(i)
        exit()

Solution (Python):
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce


INF = float('inf')
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return sys.stdin.readline().strip()
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007



n = I()
A = LI()
dp = 1
for a in A:
    dp |= dp << a

b = bin(dp)

s = sum(A)
for i in range((s + 1)//2, s + 1):
    if 1 << i & dp:
        print(i)
        break

Solution (Python):
import sys
input = sys.stdin.readline




import numpy as np

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

S = sum(A)

dp = np.zeros(S+1,dtype=np.bool)
dp[S] = 1
for a in A:
    dp[:-a] |= dp[a:]

answer = np.nonzero(dp[(S+1)//2:])[0][0] + (S+1)//2
print(answer)

Solution (Python):
N=int(input())
A=list(map(int,input().split()))
S=sum(A)
SET=1
for a in A:
  SET|=SET<<a
print(bin(SET)[::-1][(S+1)//2:].index("1")+(S+1)//2)

Solution (Python):
N=int(input())
A=list(map(int,input().split()))
S=sum(A)
SET=1
for a in A:
  SET|=SET<<a
print(bin(SET)[::-1][(S+1)//2:].index("1")+(S+1)//2)

Solution (Python):
from math import ceil
N = int(input())
A = [int(a) for a in input().split()]

DP = 1
for a in A:
    DP |= DP << a

Shalf = ceil(sum(A)/2)
DP >>= Shalf
for i in range(N * max(A)):
    if DP & 1:
        print(Shalf + i)
        break
    DP >>= 1

Solution (Python):
n = int(input())
A = list(map(int, input().split()))

dp = 1
for a in A:
	dp |= dp<<a

for i in range((sum(A)+1)//2, sum(A)+1):
	if (dp>>i)%2 == 1:
		print(i)
		break

Solution (Python):
n = int(input())
A = list(map(int, input().split()))

dp = 1
for a in A:
	dp |= dp<<a

for i in range((sum(A)+1)//2, sum(A)+1):
	if (dp>>i)%2 == 1:
		print(i)
		break

Solution (Python):
from math import ceil
N=int(input())
A=[int(i) for i in input().split()]
dp=1
for i in range(N):
  dp|=dp<<A[i]
S=sum(A)
hS=S//2
for i in range(hS+1)[::-1]:
  if dp&(1<<i):
    ans=i
    break
print(S-i)

Solution (Python):
from collections import defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue,datetime
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inpl(): return list(map(int, input().split()))
def inpl_s(): return list(input().split())


N = int(input())
aa = inpl()

b = 1
for a in aa:
	b |= b << a

S = sum(aa)
half = (S+1)//2
b >>= half

print((b&-b).bit_length()+half-1)

Solution (Python):
from math import ceil

N = int(input())
As = list(map(int, input().split()))


dp = 1
for A in As:
    dp |= dp << A


ans = ceil(sum(As) / 2)
dp >>= ans
while not (dp & 1):
    dp >>= 1
    ans += 1

print(ans)

Solution (Python):

N = int(input())
*A, = map(int, input().split())
S = sum(A)

b = 1
for a in A:
    b |= b << a
b >>= (S + 1) // 2
print((b & -b).bit_length() - 1 + (S + 1) // 2)

Solution (Python):

import numpy
n = int(input())
a = [int(i) for i in input().split()]
dp = 1
for i in range(0, len(a)):
	dp = (dp | (dp << a[i]))
 
asum = 0
for i in range(0, len(a)):
	asum += a[i]
 
for i in range(int((asum + 1) / 2), asum + 1):
	if (dp >> i) & 1:
		print(i)
		break

Solution (Python):
n = int(input())
a = [int(i) for i in input().split()]
dp = 1
for i in range(0, len(a)):
	dp = (dp | (dp << a[i]))

asum = 0
for i in range(0, len(a)):
	asum += a[i]

for i in range(int((asum + 1) / 2), asum + 1):
	if (dp >> i) & 1:
		print(i)
		break

Solution (Python):








n = int(input())
a = [int(i) for i in input().split()]
dp = 1
for i in range(0, len(a)):
	dp = (dp | (dp << a[i]))

asum = 0
for i in range(0, len(a)):
	asum += a[i]

for i in range(int((asum + 1) / 2), asum + 1):
	if (dp >> i) & 1:
		print(i)
		break

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







bits=1
for b in A:
  bits|=bits<<b





ans=sum(A)
ans=(ans+1)//2
bits >>= ans
while True:
  if bits&1:
    break
  else:
    bits>>=1
    ans+=1
print(ans)

Solution (Python):
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**15
mod = 10**9+7

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


def main():
    n = I()
    a = LI()
    s = sum(a)
    t = 1
    m = 2**(s//2+1) - 1
    for c in a:
        t |= t << c
    t &= m

    return s - (t.bit_length() - 1)


print(main())

Solution (Python):
n, arr, dp = int(input()), list(map(int, input().split())), 1
for a in arr:
    dp |= dp << a
ofs = (sum(arr) + 1) // 2
dp >>= ofs
print((dp & -dp).bit_length() + ofs - 1)

Solution (Python):
import sys
readline = sys.stdin.readline

N = int(readline())
A = list(map(int, readline().split()))
S = sum(A)
bits = 1
for a in A:
    bits |= bits << a
ans = (S + 1) // 2
bits >>= ans
while True:
    if bits & 1:
        print(ans)
        exit()
    bits >>= 1
    ans += 1

Solution (Python):


N = int(input())
dp = 1
asum = 0
for a in input().split(" "):
    x = int(a)
    asum += x
    dp = dp|(dp<<x)

for i in range((asum+1)//2, asum+1):
    if (dp>>i)&1:
        print(i)
        break

Solution (Python):

import math
input()
dp = 1
for x in map(int, input().split()):
    dp |= dp << x
h = math.ceil((len(format(dp, 'b')) - 1) / 2)
print(h + bin(dp >> h)[::-1].index('1'))

Solution (Python):

import math
input()
A = list(map(int, input().split()))

dp = 1
for x in A:
    dp |= dp << x

h = math.ceil(sum(A) / 2)
print(h + bin(dp >> h)[::-1].index('1'))

Solution (Python):
import math
N = int(input())
A = list(map(int, input().split()))
sumA = sum(A)
halfA = math.ceil(sumA / 2)
bitset = 1
for a in A:bitset |= bitset << a
bitset >>= halfA
i = 0
while 1:
    if bitset & 1:
        print(i + halfA)
        exit()
    bitset >>= 1
    i += 1

Solution (Python):
import math
N = int(input())
A = list(map(int, input().split()))
sumA = sum(A)
halfA = math.ceil(sumA / 2)
bitset = 1
for a in A:
    bitset |= bitset << a
bitset >>= halfA
i = 0
while 1:
    if bitset & 1:
        print(i + halfA)
        exit()
    bitset >>= 1
    i += 1

Solution (Python):
import math
N = int(input())
A = list(map(int, input().split()))

sumA = sum(A)
halfA = math.ceil(sumA / 2)
bitset = 1
for a in A:
  bitset |= bitset << a

bitset >>= halfA
i = 0
while i < halfA:
  if bitset & 1:
    print(i+halfA)
    exit()
  bitset >>= 1
  i += 1
print(i+halfA)

Solution (Python):
input()
a = list(map(int, input().split()))

dp = 1
for x in a:
  dp |= dp << x

s = sum(a)
dp >>= (s + 1) // 2
dp <<= (s + 1) // 2
dp = bin(dp)

print(len(dp) - len(dp.rstrip('0')))