'use strict';

process.stdin.resume();
process.stdin.setEncoding('utf-8');

let inputString = '';
let currentLine = 0;

process.stdin.on('data', inputStdin => {
    inputString += inputStdin;
});

process.stdin.on('end', _ => {
    inputString = inputString.trim().split('\n').map(string => {
        return string.trim();
    });

    main();
});

function readline() {
    return inputString[currentLine++];
}

function getArray(str) {
    return str.split(' ').map(x => Number(x));
}

function getInt(str) {
    return Number(str);
}

function getStrArray(str) {
    return str.split(' ').map(x => x);
}

function create2DArray(row, col,  filler = 0) {
    return Array(row)
        .fill(filler)
        .map(() => Array(col).fill(filler));
}
// ---------------------------------------



function main() {
    let [n, w] = getArray(readline());
    const arr = [];
    const dp = create2DArray(n+1, w+1, 0)

    let c = n;


    while(c--) {
        arr.push(getArray(readline()));
    }

    function solve(n1, w1) {
        //console.log(n1, w1);
        if (n1 < 0 || w1 <= 0) {
            return 0;
        }
        if (dp[n1][w1]) {
            return dp[n1][w1];
        }
        if (w1 >= arr[n1][0]) {
            dp[n1][w1] = Math.max(arr[n1][1] + solve(n1 - 1, w1 - arr[n1][0]), solve(n1 - 1, w1));
        } else {
            dp[n1][w1] = solve(n1 - 1, w1);
        }
        return dp[n1][w1];
    }

    console.log(solve(n-1, w));
}