import scala.io.StdIn._
object Main extends App {
  val Array(n, ww) = readLine.split(" ").map(_.toInt)
  val w = new Array[Int](n)
  val v = new Array[Int](n)
  (0 until n).foreach { i =>
    readLine.split(" ").map(_.toInt) match {
      case Array(a, b) => {
        w(i) = a
        v(i) = b
      }
    }
  }

  val dp = Array.fill(n + 1, ww + 1)(0L)
  for {
    i <- 0 until n
    j <- 0 to ww
  } {
    dp(i + 1)(j) = if (j >= w(i)) {
      math.max(dp(i)(j - w(i)) + v(i), dp(i)(j))
    } else {
      dp(i)(j)
    }
  }

  println(dp(n)(ww))

}
