import scala.io.StdIn.readLine

object Main{
  def main(args : Array[String]): Unit ={
    val Array(nN, wW) : Array[Int] = readLine().split(' ').map(_.toInt)
    val w, v : Array[Int] = Array.fill(nN + 1)(0)
    for(i <- 1 to nN){
      val Array(p, q) : Array[Int] = readLine().split(' ').map(_.toInt)
      w(i) = p
      v(i) = q
    }
    subMain(nN, wW, w, v).solve()
  }
}

case class subMain(N : Int, W : Int, w : Array[Int], v : Array[Int]){
  val hasDone : Array[Map[Int, Long]] = Array.fill(N + 1)(Map.empty)
  def Calculate(n : Int, k : Int): Unit ={
    if(hasDone(n).contains(k)) return // 計算済みのものは終了
    if(n == 0) hasDone(0) += k -> 0
    else{
      if(!hasDone(n - 1).contains(k)) Calculate(n - 1, k)
      if(k >= w(n)){
        if(!( hasDone(n - 1).contains(k - w(n)) ) ) Calculate(n - 1, k - w(n))
        hasDone(n) += (k -> math.max(hasDone(n - 1)(k), hasDone(n - 1)(k - w(n))+ v(n) ) )
      }
      else hasDone(n) += (k -> hasDone(n - 1)(k))
    }
  }
  def solve(): Unit ={
    Calculate(N, W)
    println(hasDone(N)(W))
  }
}