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: # coding: utf-8
  import re
  import math
  import itertools
  from copy import deepcopy
  import fractions
  import random
  from functools import lru_cache
  from heapq import heappop, heappush
  import time
  import sys
  
  readline = sys.stdin.readline
  sys.setrecursionlimit(2000)
  # import numpy as np
  alphabet = "abcdefghijklmnopqrstuvwxyz"
  mod = int(10**9 + 7)
  inf = int(10**20)
  
  
  def yn(b):
      if b:
          print("yes")
      else:
          print("no")
  
  
  def Yn(b):
      if b:
          print("Yes")
      else:
          print("No")
  
  
  def YN(b):
      if b:
          print("YES")
      else:
          print("NO")
  
  
  class union_find:
      def __init__(self, n):
          self.n = n
          self.P = [a for a in range(N)]
          self.rank = [0] * n
  
      def find(self, x):
          if x != self.P[x]:
              self.P[x] = self.find(self.P[x])
          return self.P[x]
  
      def same(self, x, y):
          return self.find(x) == self.find(y)
  
      def link(self, x, y):
          if self.rank[x] < self.rank[y]:
              self.P[x] = y
          elif self.rank[y] < self.rank[x]:
              self.P[y] = x
          else:
              self.P[x] = y
              self.rank[y] += 1
  
      def unite(self, x, y):
          self.link(self.find(x), self.find(y))
  
      def size(self):
          S = set()
          for a in range(self.n):
              S.add(self.find(a))
          return len(S)
  
  
  def bin_(num, size):
      A = [0] * size
      for a in range(size):
          if (num >> (size - a - 1)) & 1 == 1:
              A[a] = 1
          else:
              A[a] = 0
      return A
  
  
  def fac_list(n, mod_=0):
      A = [1] * (n + 1)
      for a in range(2, len(A)):
          A[a] = A[a - 1] * a
          if mod > 0:
              A[a] %= mod_
      return A
  
  
  def comb(n, r, mod, fac):
      if n - r < 0:
          return 0
      return (fac[n] * pow(fac[n - r], mod - 2, mod) * pow(fac[r], mod - 2, mod)) % mod
  
  
  def next_comb(num, size):
      x = num & (-num)
      y = num + x
      z = num & (~y)
      z //= x
      z = z >> 1
      num = y | z
      if num >= (1 << size):
          return False
      else:
          return num
  
  
  def get_primes(n, type="int"):
      A = [True] * (n + 1)
      A[0] = False
      A[1] = False
      for a in range(2, n + 1):
          if A[a]:
              for b in range(a * 2, n + 1, a):
                  A[b] = False
      if type == "bool":
          return A
      B = []
      for a in range(n + 1):
          if A[a]:
              B.append(a)
      return B
  
  
  def is_prime(num):
      if num <= 2:
          return False
      i = 2
      while i * i <= num:
          if num % i == 0:
              return False
          i += 1
      return True
  
  
  def join(A, c=" "):
      n = len(A)
      A = list(map(str, A))
      s = ""
      for a in range(n):
          s += A[a]
          if a < n - 1:
              s += c
      return s
  
  
  # main
  N, w = map(int, input().split())
  W = [0] * N
  V = [0] * N
  for a in range(N):
      W[a], V[a] = map(int, input().split())
  dp = [[0 for _ in range(w + 1)] for _ in range(N + 1)]
  
  for a in range(1, N + 1):
      for b in range(1, w + 1):
          if b - W[a - 1] >= 0:
              dp[a][b] = max(dp[a - 1][b], dp[a - 1][b - W[a - 1]] + V[a - 1])
          else:
              dp[a][b] = dp[a - 1][b]
  print(dp[N][w])
  
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": "5 5\n    1 1000000000\n    1 1000000000\n    1 1000000000\n    1 1000000000\n    1 1000000000", "output": "5000000000\n    \n\nThe answer may not fit into a 32-bit integer type.\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."}]