import scala.io.StdIn._

object Main extends App {


  val Array(n,w) = readLine().split(" ").map(_.toInt)
  val wv = Array.fill(n)(readLine().split(" ").map(_.toInt))
  def solve() = {
    rec(w, 0)
  }

  val dp = Array.fill(w+1)(Array.fill(n+1)(-1L))

  def rec(restW: Int, i: Int): Long = {
    if(dp(restW)(i) != -1) dp(restW)(i)
    else {
      val value = if(i == n) 0
      else {
        if(restW >= wv(i)(0)) {
          Math.max(rec(restW, i+1), rec(restW - wv(i)(0), i+1) + wv(i)(1))
        } else rec(restW, i+1)
      }
      dp(restW)(i) = value
      value
    }
  }

  println(solve())

}

