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)).toList
  type Item = (Int,Int)

  class DP(wgt:Int, items:List[Item]) {
    val memo = Array.fill(wgt+1)(0)
    def solver():Int = {
      for ((v, w) <- items) {
        for (i <- w to wgt) {
          val v0 = memo(i-w) + v
          if (v0 > memo(i)) memo(i) = v0  
        }
      }
      memo(wgt)
    }
  }
  
  val dp = new DP(W, items)

  println(dp.solver())
}
