#include <fstream>
using namespace std;
int i,j,n,g,v2[2][10005],v[5005],v3[5005];
int main()
{ifstream q("rucsac.in");
ofstream w("rucsac.out");
q>>n>>g;
for(i=1;i<=n;++i)
  q>>v[i]>>v3[i];
for(i=1;i<=n;++i)
  for(j=0;j<=g;++j)
	if(j<v[i])
	 v2[i&1][j]=v2[(i&1)^1][j];
	else
	 v2[i&1][j]=max(v2[(i&1)^1][j],v2[(i&1)^1][j-v[i]]+v3[i]);
w<<v2[n&1][g];
return 0;}