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: """ ===============================
      -- @uthor : Kaleab Asfaw
      -- Handle : kaleabasfaw2010
      -- Bio    : High-School Student
      ==============================="""
  
  # Fast IO
  import sys
  import os
  from io import BytesIO, IOBase
  
  BUFSIZE = 8192
  
  
  class FastIO(IOBase):
      newlines = 0
  
      def __init__(self, file):
          self._fd = file.fileno()
          self.buffer = BytesIO()
          self.writable = "x" in file.mode or "r" not in file.mode
          self.write = self.buffer.write if self.writable else None
  
      def read(self):
          while True:
              b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
              if not b:
                  break
              ptr = self.buffer.tell()
              self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
          self.newlines = 0
          return self.buffer.read()
  
      def readline(self):
          while self.newlines == 0:
              b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
              self.newlines = b.count(b"\n") + (not b)
              ptr = self.buffer.tell()
              self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
          self.newlines -= 1
          return self.buffer.readline()
  
      def flush(self):
          if self.writable:
              os.write(self._fd, self.buffer.getvalue())
              self.buffer.truncate(0), self.buffer.seek(0)
  
  
  class IOWrapper(IOBase):
      def __init__(self, file):
          self.buffer = FastIO(file)
          self.flush = self.buffer.flush
          self.writable = self.buffer.writable
          self.write = lambda s: self.buffer.write(s.encode("ascii"))
          self.read = lambda: self.buffer.read().decode("ascii")
          self.readline = lambda: self.buffer.readline().decode("ascii")
  
  
  sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)
  input = lambda: sys.stdin.readline().rstrip("\r\n")
  # Others
  # from math import floor, ceil, gcd
  # from decimal import Decimal as d
  mod = 10**9 + 7
  
  
  def lcm(x, y):
      return (x * y) / (gcd(x, y))
  
  
  def fact(x, mod=mod):
      ans = 1
      for i in range(1, x + 1):
          ans = (ans * i) % mod
      return ans
  
  
  def arr2D(n, m, default=0):
      lst = []
      for i in range(n):
          temp = [default] * m
          lst.append(temp)
      return lst
  
  
  def sortDictV(x):
      return {k: v for k, v in sorted(x.items(), key=lambda item: item[1])}
  
  
  def solve(n, W, weight, value):
      dp = arr2D(n + 1, W + 1)
  
      for i in range(1, n + 1):
          for j in range(1, W + 1):
              # print(i, j)
              val = max(dp[i][j - 1], dp[i - 1][j])
              if j >= weight[i - 1]:
                  dp[i][j] = max(val, dp[i - 1][j - weight[i - 1]] + value[i - 1])
              else:
                  dp[i][j] = val
      return dp[n][W]
  
  
  n, W = list(map(int, input().split()))
  weight = []
  value = []
  for i in range(n):
      a, b = list(map(int, input().split()))
      weight.append(a)
      value.append(b)
  print(solve(n, W, weight, value))
  
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."}]