import java.io._

object Main extends App {
  val in = new BufferedReader(new InputStreamReader(System.in))

  val Array(n,cp) = in.readLine.split(" ").map(_.toInt)

  val ans = {
    val dp = Array.ofDim[Int](n+1, cp+1)

    Iterator.continually(in.readLine)
    .take(n)
    .map(_.split(" "))
    .foldLeft(0)((i,e) => {
      val v = e(0).toInt
      val w = e(1).toInt
      for(j <- 1 to cp) {
        dp(i+1)(j) =
          if (w <= j && dp(i)(j) < dp(i+1)(j-w) + v) { dp(i+1)(j-w) + v }
          else dp(i)(j)
      }
      i + 1
    })

    dp(n)(cp)
  }

  println(ans)
}
