#include <fstream>
#include <string>
#include <vector>

using namespace std;


string const inFile = "rucsac.in";
string const outFile = "rucsac.out";

ifstream Read(inFile);
ofstream Write(outFile);


int main() {
    unsigned n;
    unsigned G;

    Read >> n;
    Read >> G;

    vector<vector<unsigned>> lines(2, vector<unsigned>(G + 1, 0));
    bool _switch = true;
    unsigned weight;
    unsigned value;
    unsigned i, j;

    for (i = 0; i < n; ++i) {
        Read >> weight;
        Read >> value;

        for (j = 0; j < weight; ++j) {
            lines[_switch][j] = lines[!_switch][j];
        }

        for (j = weight; j <= G; ++j) {
            lines[_switch][j] = max(lines[!_switch][j], lines[!_switch][j - weight] + value);
        }

        _switch = !_switch;
    }

    Write << lines[!_switch][G];

    return 0;
}