import java.util.Scanner

class DP(n:Int, w:Int, items:Array[(Int,Int)]) {
  val memo = Array.fill(n+1)(Array.fill(w+1)(0))
  def solver():Int = {
    for (i <- 1 to n; j <- 1 to w) {
      val (v, w) = items(i-1)
      val v0 = memo(i-1)(j)
      val v1 = if (j < w) 0 else memo(i-1)(j-w) + v
      memo(i)(j)= if (v0 > v1) v0 else v1
    }
    // for (r <- 0 to n) println(memo(r).mkString(" "))
    memo(n)(w)
  }
}

object Main extends App { 
  val sc = new Scanner(System.in)
  val N, W = sc.nextInt()
  val items = (for (i <- 1 to N) yield (sc.nextInt, sc.nextInt)).toArray

  val dp = new DP(N, W, items)

  println(dp.solver())
}
