#include <fstream>
using namespace std;
ifstream fi("rucsac.in");
ofstream fo("rucsac.out");
int best[5001][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];


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

   }

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




return 0;
}