import scala.io.Source

object Main {
  def main(args: Array[String]): Unit = {
    val lines = Source.stdin.getLines.toStream
    val Array(numLines, weightMax) = lines.head.split(" ").map(_.toInt)
    val valueWeight = lines.drop(1).take(numLines).map{ v =>
      val Array(value, weight) = v.split(" ").map(_.toInt)
      (value, weight)
    }.toArray
    val memo = (new Array[Int]((numLines+1) * (weightMax+1))).map(_ => -1)
    println(dp(numLines - 1, weightMax, valueWeight, memo, numLines, weightMax))
    // println(memo.toList)
  }

  def dp(i: Int, j: Int, arr: Array[(Int, Int)], memo: Array[Int], width: Int, height: Int): Int = {
    if (i < 0 || j == 0) {
      0
    } else if (memo(width*j + i) != -1) {
      memo(width*j + i)
    } else {
      if (j >= arr(i)._2) {
        memo(width*j + i) =
          math.max(
            dp(i - 1, j, arr, memo, width, height),
            dp(i - 1, j - arr(i)._2, arr, memo, width, height) + arr(i)._1
          )
      } else {
        memo(width*j + i) = dp(i - 1, j, arr, memo, width, height)
      }
      if (memo(width*j + i) == -1) memo(width*j + i) = 0
      memo(width*j + i)
    }
  }
}

