// inputに入力データ全体が入る
var dp = new Array(1001);
for(var temp =0; temp < 1001; temp++){
    dp[temp] = new Array(1001);
    for(var temp2 = 0; temp2<1001; temp2++){
        dp[temp][temp2] = -1;
    }
}


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] = lins[0];
        values[i] = lins[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]);
    }

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

    var ans = recursive(0,limitweight,maxnum,weights,values);

    console.log(ans);
}



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