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 -*-
  
  #############
  # Libraries #
  #############
  
  import sys
  
  input = sys.stdin.readline
  
  import math
  
  # from math import gcd
  import bisect
  import heapq
  from collections import defaultdict
  from collections import deque
  from collections import Counter
  from functools import lru_cache
  
  #############
  # Constants #
  #############
  
  MOD = 10**9 + 7
  INF = float("inf")
  AZ = "abcdefghijklmnopqrstuvwxyz"
  
  #############
  # Functions #
  #############
  
  
  ######INPUT######
  def I():
      return int(input().strip())
  
  
  def S():
      return input().strip()
  
  
  def IL():
      return list(map(int, input().split()))
  
  
  def SL():
      return list(map(str, input().split()))
  
  
  def ILs(n):
      return list(int(input()) for _ in range(n))
  
  
  def SLs(n):
      return list(input().strip() for _ in range(n))
  
  
  def ILL(n):
      return [list(map(int, input().split())) for _ in range(n)]
  
  
  def SLL(n):
      return [list(map(str, input().split())) for _ in range(n)]
  
  
  ######OUTPUT######
  def P(arg):
      print(arg)
      return
  
  
  def Y():
      print("Yes")
      return
  
  
  def N():
      print("No")
      return
  
  
  def E():
      exit()
  
  
  def PE(arg):
      print(arg)
      exit()
  
  
  def YE():
      print("Yes")
      exit()
  
  
  def NE():
      print("No")
      exit()
  
  
  #####Shorten#####
  def DD(arg):
      return defaultdict(arg)
  
  
  #####Inverse#####
  def inv(n):
      return pow(n, MOD - 2, MOD)
  
  
  ######Combination######
  kaijo_memo = []
  
  
  def kaijo(n):
      if len(kaijo_memo) > n:
          return kaijo_memo[n]
      if len(kaijo_memo) == 0:
          kaijo_memo.append(1)
      while len(kaijo_memo) <= n:
          kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
      return kaijo_memo[n]
  
  
  gyaku_kaijo_memo = []
  
  
  def gyaku_kaijo(n):
      if len(gyaku_kaijo_memo) > n:
          return gyaku_kaijo_memo[n]
      if len(gyaku_kaijo_memo) == 0:
          gyaku_kaijo_memo.append(1)
      while len(gyaku_kaijo_memo) <= n:
          gyaku_kaijo_memo.append(
              gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo), MOD - 2, MOD) % MOD
          )
      return gyaku_kaijo_memo[n]
  
  
  def nCr(n, r):
      if n == r:
          return 1
      if n < r or r < 0:
          return 0
      ret = 1
      ret = ret * kaijo(n) % MOD
      ret = ret * gyaku_kaijo(r) % MOD
      ret = ret * gyaku_kaijo(n - r) % MOD
      return ret
  
  
  ######Factorization######
  def factorization(n):
      arr = []
      temp = n
      for i in range(2, int(-(-(n**0.5) // 1)) + 1):
          if temp % i == 0:
              cnt = 0
              while temp % i == 0:
                  cnt += 1
                  temp //= i
              arr.append([i, cnt])
      if temp != 1:
          arr.append([temp, 1])
      if arr == []:
          arr.append([n, 1])
      return arr
  
  
  #####MakeDivisors######
  def make_divisors(n):
      divisors = []
      for i in range(1, int(n**0.5) + 1):
          if n % i == 0:
              divisors.append(i)
              if i != n // i:
                  divisors.append(n // i)
      return divisors
  
  
  #####MakePrimes######
  def make_primes(N):
      max = int(math.sqrt(N))
      seachList = [i for i in range(2, N + 1)]
      primeNum = []
      while seachList[0] <= max:
          primeNum.append(seachList[0])
          tmp = seachList[0]
          seachList = [i for i in seachList if i % tmp != 0]
      primeNum.extend(seachList)
      return primeNum
  
  
  #####GCD#####
  def gcd(a, b):
      while b:
          a, b = b, a % b
      return a
  
  
  #####LCM#####
  def lcm(a, b):
      return a * b // gcd(a, b)
  
  
  #####BitCount#####
  def count_bit(n):
      count = 0
      while n:
          n &= n - 1
          count += 1
      return count
  
  
  #####ChangeBase#####
  def base_10_to_n(X, n):
      if X // n:
          return base_10_to_n(X // n, n) + [X % n]
      return [X % n]
  
  
  def base_n_to_10(X, n):
      return sum(int(str(X)[-i - 1]) * n**i for i in range(len(str(X))))
  
  
  def base_10_to_n_without_0(X, n):
      X -= 1
      if X // n:
          return base_10_to_n_without_0(X // n, n) + [X % n]
      return [X % n]
  
  
  #####IntLog#####
  def int_log(n, a):
      count = 0
      while n >= a:
          n //= a
          count += 1
      return count
  
  
  #############
  # Main Code #
  #############
  
  N, W = IL()
  data = ILL(N)
  
  dp = [[0 for w in range(W + 1)] for i in range(N + 1)]
  
  for i in range(N):
      w0, v0 = data[i]
      for w in range(W):
          if w + w0 <= W:
              dp[i + 1][w + w0] = max(dp[i][w + w0], dp[i][w] + v0)
  
  print(max(dp[-1]))
  
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."}]