#include <iostream>
#include <fstream>

using namespace std;

ifstream in("rucsac.in");
ofstream out("rucsac.out");

struct item {
    int G;
    int V;
};

item it[5003];
int mat[10003];

int main() {

    int n,g;
    in >> n >> g;

    for(int i = 1; i <= n; i++)
        in >> it[i].G >> it[i].V;

    for(int i = 1; i <= n; i++)
        for(int j = g; j >= it[i].G; j--)
            mat[j] = max(mat[j], mat[j-it[i].G]+it[i].V);

    out << mat[g];

    return 0;
}