#include <iostream>
#include <fstream>
using namespace std;

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

int g[2][10005],N,G;

int main()
{
    fin>>N>>G;
    int i,j,p,w;
    int *prevrow=g[0];
    int *currow=g[1];
    for(i=1;i<=N;i++)
        {
            fin>>w>>p;
            for(j=G;j>=w;j--)
                currow[j]=max(prevrow[j],prevrow[j-w]+p);
            for(j;j>=0;j--)
                currow[j]=prevrow[j];

            /*
            for(j=1;j<=G;j++)
                cout<<prevrow[j]<<' ';
            cout<<endl;
            for(j=1;j<=G;j++)
                cout<<currow[j]<<' ';
            cout<<endl;
            cout<<endl;
            */
            swap(prevrow,currow);
        }
    fout<<g[0][G];
}