#include <iostream>
#include <fstream>
using namespace std;
ifstream f("rucsac.in");
ofstream out("rucsac.out");
int n,g,w[5001],p[5001],prof[10010],i,j;
int main()
{
    f>>n>>g;
    for(i=1; i<=n; ++i)
    {
        f>>w[i];
        f>>p[i];
    }
    prof[0]=0;
    int sol=0;
    for(i=1; i<=n; i++)
        for(j=g-w[i]; j>=0; j--)
        {
            if(prof[j+w[i]] < prof[j] + p[i] )
            {
                prof[j+w[i]] = prof[j] + p[i];
                if (prof[j + w[i]] > sol)
                    sol = prof[j + w[i]];
            }
        }

    out<<sol;
    return 0;
}