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 lines, the
  value and weight of the i-th item are given.
attempt: def loadItems():
      items = []
      N, maxW = [int(i) for i in input().strip().split()]
      while True:
          item = {}
          item["v"], item["w"] = [int(i) for i in input().strip().split()]
          items.append(item)
          if len(items) == N:
              break
      return maxW, items
  
  
  def calc(maxW, items):
      memo = [0] * (maxW + 1)
      for item in items:
          for W in range(maxW + 1):
              if W + item["w"] <= maxW:
                  if (maxW - W) % item["w"] == 0:
                      memo[W + item["w"]] = max(memo[W] + item["v"], memo[W + item["w"]])
                  else:
                      memo[W] = max(memo[W], memo[W - 1])
  
      return memo
  
  
  maxW, items = loadItems()
  print(max(calc(maxW, items)))
  
problem_description: Knapsack Problem
  
    
  
  You have N kinds of 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.
    * You can select as many items as possible into a knapsack for each kind.
  
  Find the maximum total value of items in the knapsack.
samples: [{"input": "4 8\n    4 2\n    5 2\n    2 1\n    8 3", "output": "21"}, {"input": "2 20\n    5 9\n    4 10", "output": "10"}, {"input": "3 9\n    2 1\n    3 1\n    5 2", "output": "27"}]