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

lc=1;lp=0;
for(i=1;i<=n;i++)
{fi>>w>>p;

for(j=0;j<=g;j++)
   { best[lc][j] = best[lp][j];

    if(j - w>=0)
     best[lc][j]=max( best[lc][j],best[lp][j - w] + p);
    }
swap(lc,lp);
}
fo<<best[lp][g]<<'\n';


return 0;
}