#include <fstream>

using namespace std;

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

int sol, n, G, i, j, w[10002], g[10002], opt[10002];

int main()
{
    fin>>n>>G;
    for(i=1; i<=n; ++i) fin>>w[i]>>g[i];

    for(i=1; i<=n; ++i)
    {
        for(j=G-w[i]; j>=0; --j)
           if(opt[j+w[i]]<opt[j]+g[i])
           {
               opt[j+w[i]]=opt[j]+g[i];
               if(opt[j+w[i]]>sol) sol=opt[j+w[i]];
           }
    }

    fout<<sol<<"\n";
}