// inputに入力データ全体が入る

function Main(input) {
    input = input.split("\n");
    var line1 = input[0].split(" ");
    var maxnum = parseInt(line1[0]);
    var limitweight = parseInt(line1[1]);

    var weights = [];
    var values = [];

    for(var i = 0; i < maxnum; i++){
        var lins = input[i+1].split(" ");
        weights[i] = parseInt(lins[0]);
        values[i] = parseInt(lins[1]);
    }
    
//    console.log(values);

    var dp = new Array(maxnum);
    for(var temp =0; temp <= maxnum; temp++){
        dp[temp] = new Array(limitweight);
        for(var temp2 = 0; temp2<=limitweight; temp2++){
            dp[temp][temp2] = -1;
        }
    }

    function recursive(num,weight){
    if(dp[num][weight] >= 0){
        return dp[num][weight];
    }

    var result = 0;

    if (num === maxnum){
        result = 0;
    } else if (weight < weights[num]){
        result = recursive(num+1,weight);
    } else {
        result = Math.max(recursive(num + 1, weight), recursive(num + 1, weight - weights[num]) + values[num]);
    }

//    console.log("n:"+num+" w:"+weight+" result:"+result);


    return dp[num][weight] = result;
    }

    var ans = recursive(0,limitweight);

    console.log(ans);
//    console.log(dp);
}



//*この行以降は編集しないでください（標準入出力から一度に読み込み、Mainを呼び出します）
Main(require("fs").readFileSync("/dev/stdin", "utf8"));