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())
  M = 10**4
  dp = [0] * (2 * M)
  dp[M] = 1
  A = tuple(map(int, input().split()))
  for i, a in enumerate(A):
      for j in range(2 * M):
          if j - a >= 0 and dp[j - a]:
              dp[j] = 1
  l = sum(divmod(sum(A), 2))
  now = M + l
  while True:
      if dp[now]:
          print(now - M)
          break
      now += 1
  
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)."}]