#include <fstream>

using namespace std;

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

int n, G, D[5001][10001];

struct obiect {
    int val, greu;
}v[5001];

int main () {
    fin >> n >> G;
    for (int i = 1; i <= n; i++)
        fin >> v[i].greu >> v[i].val;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= G; j++) {
            D[i][j] = D[i-1][j];
            if (v[i].greu <= j) {
                D[i][j] = max(D[i][j], D[i-1][j - v[i].greu] + v[i].val);
            }
        }
    }
    /*for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= G; j++) {
            fout << D[i][j] << " ";
        }
        fout << '\n';
    }*/
    fout << D[n][G];
}