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: import bisect
  
  n, knapsack = map(int, input().split())
  items = [tuple(map(int, input().split())) for _ in range(n)]
  
  
  def make_half_knapsack(hn, items):
      hk = {}
      for i in range(1, 1 << hn):
          vs, ws = 0, 0
          j, k = i, 0
          while j:
              if j & 1:
                  v, w = items[k]
                  vs += v
                  ws += w
              j >>= 1
              k += 1
          if ws not in hk or hk[ws] < vs:
              hk[ws] = vs
      return hk
  
  
  hn = n // 2
  hk = make_half_knapsack(hn, items[:hn])
  hk1w = sorted(hk.keys())
  hk1v = [hk[w] for w in hk1w]
  
  hk = make_half_knapsack(n - hn, items[hn:])
  ans = 0
  
  for w2, v2 in hk.items():
      i = bisect.bisect(hk1w, knapsack - w2)
      ans = max(ans, max(hk1v[:i], default=0) + v2)
  
  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"}]