import scala.io.StdIn.readLine;
object Main {
    def main(args: Array[String]): Unit = {
        val Array(n, w) = readLine.split(" ").map(_.toInt);
        val baggege = new Array[Array[Int]](n);
        for ( i <- (0 until n)) {
            baggege(i) = readLine.split(" ").map(_.toInt); // [value, weight]
        }
        println(knapsackProblem(n, w, baggege));
    }
    def knapsackProblem(n: Int, w: Int, baggege: Array[Array[Int]]): Int = {
        val matrix = Array.ofDim[Int](n + 1, w + 1);
        for (row <- (1 to n); col <- (1 to w)) {
            val currValue = baggege(row - 1)(0);
            val currWeight = baggege(row - 1)(1);
            matrix(row)(col) = if (col >= currWeight) {
                // row番目の荷物を使わない場合 : (row - 1) 番目までの荷物を使って col(weight) に詰め込める価値の最大
                // row番目の荷物を使う場合 : row 番目の荷物の価値 + (col - currWeight) に詰め込める価値の最大
                Math.max(matrix(row - 1)(col), matrix(row - 1)(col - currWeight) + currValue);
            } else {
                matrix(row - 1)(col);
            }
        }
        matrix(n)(w);
    }
}
