#include <fstream>
#define NMAX 5002
#define GMAX 10002

using namespace std;

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

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

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;
        }
}