#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[5003][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[i][j] = mat[i-1][j];
            } else {
                mat[i][j] = max(mat[i-1][j], mat[i-1][j-it[i].G]+it[i].V);
            }

        }

    }

    out << mat[n][g];

    return 0;
}