#include <iostream>
#include <fstream>
using namespace std;
int N,G,d[5001],sol;
int main()
{
   int i,j,x,y;
    ifstream f("rucsac.in");
    ofstream g("rucsac.out");
    f>>N>>G;
    for(i=1;i<=N;i++)
    {
        f>>x>>y;
        for(j=G-x;j>=0;j--)
        {
            if(d[j+x]<d[j]+y)
                d[j+x]=d[j]+y;
            if(d[j+x]>sol)
                sol=d[j+x];

        }
    }
    g<<sol;
    return 0;
}