object Main {
  def main(args: Array[String]): Unit = {
    val (num, limit) = {
      val nw = io.StdIn.readLine().split(" ").map(_.toInt)
      (nw(0), nw(1))
    }
    val items = new Array[(Int, Int)](num)
    for (i <- 0 until num) {
      val vw = io.StdIn.readLine().split(" ").map(_.toInt)
      items(i) = (vw(0), vw(1))
    }

    val dp = solve(limit, items)
    println(dp(num)(limit))
  }

  def solve(limit: Int, items: Array[(Int, Int)]): Array[Array[Int]] = {
    val dp = Array.ofDim[Int](items.length + 1, limit + 1)

    items.zipWithIndex.foreach { case ((v, w), i) =>
      for (l <- 1 to limit) {
        if (w <= l && dp(i)(l) < dp(i + 1)(l - w) + v) {
          dp(i + 1)(l) = dp(i + 1)(l - w) + v
        } else {
          dp(i + 1)(l) = dp(i)(l)
        }
      }
    }
    dp
  }
}