#include <fstream>
using namespace std;
ifstream f("rucsac.in");
ofstream g("rucsac.out");
int N,G,W[6000],P[6000],s[10002],p,Smax,Max;
int main()
{
    f>>N>>G;
    Smax=0;
    for(int i=1; i<=N; i++)
    {
        f>>W[i]>>P[i];
        Smax+=W[i];
    }
//    for(int i=1; i<=Smax; i++)
  //      s[i]=-1;
    s[0]=0;
    for(int i=1; i<=N; i++)
    {
      if(G-W[i])
        for(int j=G-W[i]; j>=0; j--)
            if(/*s[j]!=-1 && */s[j+W[i]] < s[j]+P[i])
            {
                s[j+W[i]]=s[j]+P[i];
                if(s[j+W[i]]>Max)
                    Max=s[j+W[i]];
            }
    }
    g<<Max<<'\n';
    return 0;
}