#include <fstream>
using namespace std;
ifstream fi("rucsac.in");
ofstream fo("rucsac.out");
int best[2][10001],w[5001],p[5001],i,j,n,g,lc,lp;
int main()
{
fi>>n>>g;
for(i=1;i<=n;i++) fi>>w[i]>>p[i];

lc=1;lp=0;
for(i=1;i<=n;i++)
   {
for(j=1;j<=g;j++)
 if(j - w[i]>=0)
   best[lc][j]=max( best[lp][j],best[lp][j - w[i]] + p[i]);
swap(lc,lp);
   }

fo<<best[lp][g]<<'\n';


//for(i=1;i<=n;i++,fo<<'\n')
//    for(j=1;j<=g;j++) fo<<best[i][j]<<" ";

return 0;
}