import sys

input = sys.stdin.readline



# 集合Sと補集合を対応 → 空、全体を除くと完全に対応

# 和がsum(A)/2)以上での最小値



import numpy as np



N = int(eval(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)



import sys



read = sys.stdin.buffer.read

readline = sys.stdin.buffer.readline

readlines = sys.stdin.buffer.readlines



N, *A = list(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)
import sys

input = sys.stdin.readline
# 集合Sと補集合を対応 → 空、全体を除くと完全に対応
# 和がsum(A)/2)以上での最小値
import numpy as np

N = int(eval(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)

import sys

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
N, *A = list(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)

-input = sys.stdin.readline -# 集合Sと補集合を対応 → 空、全体を除くと完全に対応 -# 和がsum(A)/2)以上での最小値 -import numpy as np - -N = int(eval(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) +read = sys.stdin.buffer.read +readline = sys.stdin.buffer.readline +readlines = sys.stdin.buffer.readlines +N, *A = list(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)