output_description: Print the maximum possible sum of the values of items that Taro takes home.
  
  * * *
input_description: Input is given from Standard Input in the following format:
  
      
      
      N W
      w_1 v_1
      w_2 v_2
      :
      w_N v_N
attempt: def knapsack_price(single=True):
      """
      重さが小さい時のナップサックDP
      :param single: True = 重複なし
      """
      """ dp[price <= V] = 価値を固定した時の最小重量 """
      V = sum(price_list)
      dp_max = W + 1
      dp = [dp_max] * (V + 1)
      dp[0] = 0  # 境界条件：　価値0 の時は重さは0
  
      for item in range(N):
          if single:
              S = reversed(range(price_list[item], V + 1))
          else:
              S = range(price_list[item], V + 1)
          for price in S:
              dp[price] = min2(
                  dp[price], dp[price - price_list[item]] + weight_list[item]
              )
      return max(price for price in range(V + 1) if dp[price] <= W)
  
  
  #######################################################################################################
  import sys
  
  input = sys.stdin.readline
  
  
  def max2(x, y):
      """pythonの組み込み関数 max は2変数に対しては遅い！！"""
      if x > y:
          return x
      else:
          return y
  
  
  def min2(x, y):
      """pythonの組み込み関数 min は2変数に対しては遅い！！"""
      if x < y:
          return x
      else:
          return y
  
  
  N, W = map(int, input().split())  # N: 品物の種類 W: 重量制限
  
  price_list = []
  weight_list = []
  for _ in range(N):
      """price と weight が逆転して入力されている場合有り"""
      weight, price = map(int, input().split())
      price_list.append(price)
      weight_list.append(weight)
  
  print(knapsack_price(single=True))
  
problem_description: Statement
  
  There are N items, numbered 1, 2, \ldots, N. For each i (1 \leq i \leq N),
  Item i has a weight of w_i and a value of v_i.
  
  Taro has decided to choose some of the N items and carry them home in a
  knapsack. The capacity of the knapsack is W, which means that the sum of the
  weights of items taken must be at most W.
  
  Find the maximum possible sum of the values of items that Taro takes home.
samples: [{"input": "3 8\n    3 30\n    4 50\n    5 60", "output": "90\n    \n\nItems 1 and 3 should be taken. Then, the sum of the weights is 3 + 5 = 8, and\nthe sum of the values is 30 + 60 = 90.\n\n* * *"}, {"input": "1 1000000000\n    1000000000 10", "output": "10\n    \n\n* * *"}, {"input": "6 15\n    6 5\n    5 6\n    6 4\n    6 6\n    3 5\n    7 2", "output": "17\n    \n\nItems 2, 4 and 5 should be taken. Then, the sum of the weights is 5 + 6 + 3 =\n14, and the sum of the values is 6 + 6 + 5 = 17."}]