#include <fstream>
#include <algorithm>
using namespace std;
ifstream f("rucsac.in");
ofstream G("rucsac.out");
int a[5010],b[5010],n,g,c[2][10010],i,j;
int main ()
{
	f>>n>>g;
	for (i=1;i<=n;i++) f>>a[i]>>b[i];
	for (i=1;i<=n;i++)
	{
		for (j=0;j<=g;j++)
		{
			c[1][j]=c[0][j];
			if (a[i]<=j)
				c[1][j]=max(c[1][j],c[0][j-a[i]]+b[i]);
		}
	   for (j=0;j<=g;j++)
		   c[0][j]=c[1][j];
	}
	
	G<<c[1][g]<<'\n';
return 0;
}