#include <fstream>
#define GMAX 10010
#define NMAX 5004

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

int g[NMAX], p[NMAX];
int pmax[2][2*NMAX];
int n, Gmax, maxim;

void citire(), pd(), afisare();

int main()
{
citire();
pd();
afisare();
return 0;
}

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

void pd()
{
int i, G, lc=1, lp=0;
//initializari
for (G=1; G<=Gmax; G++)
    if (g[1]<=G) pmax[lp][G]=p[1];
    else pmax[lp][G]=0;
// pd
for (i=2; i<=n; i++)
    {for (G=1; G<=Gmax; G++)
        {
            maxim=pmax[lp][G];
            if (g[i]<=G && maxim<p[i]+pmax[lp][G-g[i]])
                maxim=p[i]+pmax[lp][G-g[i]];
            pmax[lc][G]=maxim;
        }
    lc=1-lc; lp=1-lp;
    }
}

void afisare()
{
fout<<maxim<<'\n';
fout.close();
}