#include <fstream>

using namespace std;

ifstream f("rucsac.in");
ofstream g("rucsac.out");

long N,G,W[5005],P[5005],D[10005],sol;

int main()
{
    f>>N>>G;
    for (int i=1;i<=N;i++)
    f>>W[i]>>P[i];



    for (int i=1;i<=N;i++)
        for (int j=G-W[i];j>=0;j--)
          if((D[j]+P[i])>D[j+W[i]])
              {  D[j+W[i]]=D[j]+P[i];
                 if (D[j+W[i]]>sol)
                 sol=D[j+W[i]];
              }

    g<<sol;
    return 0;
}