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