#include<fstream>
#define Nmax 5009
#define Gmax 10009

using namespace std;
ifstream f("rucsac.in");
ofstream g("rucsac.out");

int N,G,gr[Nmax],p[Nmax],D[2][Gmax],k;

int main()
{
    f>>N>>G;
    for(int i=1;i<=N;i++) f>>gr[i]>>p[i];
    k=1;
    for(int i=1;i<=N;i++)
    {
        for(int cap=0;cap<=G;cap++)
        {
            D[k][cap]=D[1-k][cap]; //nu iau ob i
            if(gr[i]<=cap) // daca pot lua ob i
                if(D[k][cap]<D[1-k][cap-gr[i]]+p[i])
                    D[k][cap]=D[1-k][cap-gr[i]]+p[i];
        }
        k=1-k;

    }
    g<<D[1-k][G]<<'\n';

    f.close();g.close();
    return 0;

}