function Main(input) {
    input = input.trim().split("\n").map(function(x) { return x.split(" ")});
    let N = parseInt(input[0][0], 10);
    let W = parseInt(input[0][1], 10);
    let arr_wv = [];
    for (let i = 0; i < N; i++){
        arr_wv.push(input[i + 1].map(e => parseInt(e, 10)));
    }
    
    let DP = [Array.from({length: W + 1}, () => 0)];
    let tmpline;
    for (let i = 0; i < N; i++){
        tmpline = arr_wv[i];
        DP.push([]);
        for (let j = 0; j < tmpline[0]; j++){
            DP[i + 1].push(DP[i][j]);
        }
        for (let j = tmpline[0]; j <= W; j++){
            DP[i + 1].push(Math.max(DP[i][j], DP[i][j - tmpline[0]] + tmpline[1]));
        }
    }

    console.log(DP.pop().pop());
}


Main(require("fs").readFileSync("/dev/stdin", "utf8"));
