/*
subprobleme: profitul maxim pe care il pot obtine selectand dintre obiectele 1,2,...i fara a depasi o greutate totala G
1<=i<=n;
0<=g<=Gmax


pmax[i][G]=

pmax[i][0]=0;
pmax[1][G]={
            p[1], g[1]<=G
            0, altfel
            }

pmax[i][G]={max(
            pmax[i-1][G]
            p[i]+pmax[i-1][G-g[i]]        ,daca g[i]<=G
            )}

*/


#include <fstream>
#define NMAX 10010
using namespace std;

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

int n,G;
int g[NMAX],p[NMAX];
int pmax[2][NMAX];
int lurm,lcrt,maxi;

void pd();

int main()
{
    int i;
    fin >> n >> G;
    for(i=1;i<=n;i++)
    {
        fin >>g[i]>> p[i];  //greutate si pret
    }
    pd();
    fout << maxi << '\n';
    return 0;
}

int maxim(int a,int b)
{
    if(a>b) return a;
    return b;
}

void pd()
{
    int cat,i;
    lurm=1;
    lcrt=0;
    for(cat=1;cat<=G;cat++)
    if(g[1]<=cat)
        pmax[lcrt][cat]=p[1];
    for(i=2;i<=n;i++)
    {
        for(cat=1;cat<=G;cat++)
        {
            pmax[lurm][cat]=pmax[lcrt][cat];
            if(g[i]<=G)
                pmax[lurm][cat]=maxim(pmax[lurm][cat],p[i]+pmax[lcrt][cat-g[i]]);
            if(pmax[lurm][cat]>maxi)
                maxi=pmax[lurm][cat];
        }
        lurm=1-lurm;
        lcrt=1-lcrt;
    }
}