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 = list(map(int, input().split(" ")))
  items = [list(map(int, input().split(" "))) for i in range(n)]
  
  interim_ans = [0 for i in range(w + 1)]  # i個目までのアイテムを使う場合の暫定解
  best_ans = 0
  
  
  def branch_and_bound(
      i, putted, cr_val, cr_weight
  ):  # branch and bound: i番目の要素のありなし
      if i >= n:
          return
  
      global interim_ans, best_ans
      new_val, new_weight = cr_val, cr_weight
      if putted:
          new_val += items[i][0]
          new_weight += items[i][1]
  
      if new_weight > w:
          return
      if interim_ans[new_weight] > new_val:
          return
      if best_ans < new_val:
          best_ans = new_val
      if interim_ans[new_weight] < new_val:
          interim_ans[new_weight] = new_val
  
      branch_and_bound(i + 1, True, new_val, new_weight)
      branch_and_bound(i + 1, False, new_val, new_weight)
  
  
  branch_and_bound(0, True, 0, 0)
  branch_and_bound(0, False, 0, 0)
  
  print(best_ans)
  
problem_description: 0-1 Knapsack Problem II
  
    
  
  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"}]