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: n = int(input())
  tmp = input().split(" ")
  a = [int(tmp[i]) for i in range(n)]
  s = sum(a)
  mx = max(a)
  d = {}
  for i in range(n):
      d1 = {}
      d1[a[i]] = 1
      for x in d:
          d1[x] = 1
          if (x + a[i]) * 2 < s + mx * 2:
              d1[x + a[i]] = 1
      d = d1
  ans = mx * n
  for x in d:
      if x * x >= s:
          ans = min(ans, x)
  print(ans)
  
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)."}]