output_description: Print the median of the sorted list of the sums of all non-empty subsequences
  of A.
  
  * * *
input_description: Input is given from Standard Input in the following format:
  
      
      
      N
      A_1 A_2 ... A_N
attempt: 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) // 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
  """
  
problem_description: 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}}.
samples: [{"input": "3\n    1 2 1", "output": "2\n    \n\nIn this case, S = (1, 1, 2, 2, 3, 3, 4). Its median is S_4 = 2.\n\n* * *"}, {"input": "1\n    58", "output": "58\n    \n\nIn this case, S = (58)."}]