#include <fstream>

#define NMAX 5002
#define GMAX 10002

using namespace std;

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

int G, n, g[NMAX], c[NMAX], lc = 1, lp = 0;
int cmax[2][GMAX];

void citire();
void pd();

int main()
{
    citire();
    pd();
    fout << cmax[lp][G] << '\n';
    return 0;
}

void citire()
{
    int i;
    fin >> n >> G;
    for(i = 1; i <= n; ++i)
        fin >> g[i] >> c[i];
}

void pd()
{
    int i, x;
    for(i = 1; i <= n; ++i)
    {
        for(x = 1; x <= G; ++x)
        {
            cmax[lc][x] = cmax[lp][x];
            if(g[i] <= x && (cmax[lp][x-g[i]]+c[i] > cmax[lc][x]))
                cmax[lc][x] = cmax[lp][x-g[i]]+c[i];
        }
        lp = 1-lp;
        lc = 1-lc;
    }

}