output_description: Print the maximum total values of the items in a line.
input_description: N W
      v1 w1
      v2 w2
      :
      vN wN
      
  
  The first line consists of the integers N and W. In the following N lines, the
  value and weight of the i-th item are given.
attempt: n, W = map(int, input().split())
  value = []
  weight = []
  
  for _ in range(n):
      v, w = map(int, input().split())
      value.append(v)
      weight.append(w)
  
  
  def search(i, k, acc, vlst, wlst, vwlst):
      if i == k:
          vsum = sum(vlst[i] for i in range(k) if acc[i])
          wsum = sum(wlst[i] for i in range(k) if acc[i])
          vwlst.append([wsum, vsum])
      else:
          search(i + 1, k, acc + [0], vlst, wlst, vwlst)
          search(i + 1, k, acc + [1], vlst, wlst, vwlst)
  
  
  vw1 = []
  vw2 = []
  
  search(0, n // 2, [], value[: n // 2], weight[: n // 2], vw1)
  search(0, n - n // 2, [], value[n // 2 :], weight[n // 2 :], vw2)
  
  vw1.sort()
  vw2.sort()
  
  maxv = 0
  for i in range(n // 2):
      w, v = vw1[i]
      if maxv < v:
          maxv = v
      else:
          vw1[i][1] = maxv
  
  maxv = 0
  for i in range(n - n // 2):
      w, v = vw2[i]
      if maxv < v:
          maxv = v
      else:
          vw2[i][1] = maxv
  
  ind1 = 0
  ind2 = 2 ** (n - n // 2) - 1
  ans = 0
  while ind1 < 2 ** (n // 2) and ind2 >= 0:
      w1, v1 = vw1[ind1]
      w2, v2 = vw2[ind2]
      while ind2 > 0 and w1 + w2 > W:
          ind2 -= 1
          w2, v2 = vw2[ind2]
      if w1 + w2 <= W:
          ans = max(ans, v1 + v2)
      ind1 += 1
  
  print(ans)
  
problem_description: Huge Knapsack Problem
  
    
  
  You have N items that you want to put them into a knapsack. Item i has value
  vi and weight wi.
  
  You want to find a subset of items to put such that:
  
    * The total value of the items is as large as possible.
    * The items have combined weight at most W, that is capacity of the knapsack.
  
  Find the maximum total value of items in the knapsack.
samples: [{"input": "4 5\n    4 2\n    5 2\n    2 1\n    8 3", "output": "13"}, {"input": "2 20\n    5 9\n    4 10", "output": "9"}]