#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[2][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 = 1; j <= g; j++) {

            if(j < it[i].G) {
                mat[1][j] = mat[0][j];
            } else {
                mat[1][j] = max(mat[0][j], mat[0][j-it[i].G]+it[i].V);
            }

        }

        for(int j = 1; j <= g; j++)
            mat[0][j] = mat[1][j];

    }

    out << mat[0][g];

    return 0;
}