#include<fstream>
using namespace std;
ifstream fin("rucsac.in"); ofstream fout("rucsac.out");
int N,G,W,P,sol,D[10001];
int main()
{   fin>>N>>G;
    for(int i=1;i<=N;++i)
    {   fin>>W>>P;
        for(int j=G-W;j>=0;--j)
        {   if(D[j+W]<D[j]+P)
            {   D[j+W] =D[j]+P;
                if(sol<D[j+W]) sol=D[j+W];
            }
        }
    }
    fout<<sol; fout.close(); return 0;
}