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: n, m = map(int, input().split())
  VW = [tuple(map(int, input().split())) for i in range(n)]
  V = [v for v, w in VW]
  W = [w for v, w in VW]
  # n, m = 4, 8
  # V = [4, 5, 2, 8]
  # W = [2, 2, 1, 3]
  # DP[i][j]=i個の品物で重さj以内で最大価値
  DP = [[0 for j in range(m + 1)] for i in range(n + 1)]
  for i in range(n):
      for j in range(m + 1):
          if j < W[i]:
              DP[i + 1][j] = DP[i][j]
          else:
              DP[i + 1][j] = max(DP[i][j], DP[i + 1][j - W[i]] + V[i])
  print(DP[n][m])
  
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"}]