_,a=open(0)

*a,=list(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))
def main():

  _,a=open(0)

  *a,=list(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()
_, a = open(0)
(*a,) = list(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))

def main():
    _, a = open(0)
    (*a,) = list(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()

-_, a = open(0) -(*a,) = list(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)) +def main(): +    _, a = open(0) +    (*a,) = list(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()