import java.util.Scanner

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

  type Item = (Int,Int)

  class DP(num:Int, wgt:Int, items:Array[Item]) {
    val memo = Array.fill(wgt+1)(0)
    override def toString:String = (for (e <- memo) yield f" $e%2d").foldLeft("")(_ + _)
    def solver():Int = {
      for (i <- 1 to num; j <- wgt to 0 by -1) {
        val (v, w) = items(i-1)
        if (j >= w) {
          val v0 = memo(j)
          val v1 = memo(j-w) + v
          memo(j)= v0 max v1
        }
      }
      memo(wgt)
    }
  }
  
  val dp = new DP(N, W, items)

  println(dp.solver())
}
