#include<fstream>
using namespace std;
long sol[10001];
int main()
{
	ifstream f("rucsac.in");
	ofstream g("rucsac.out");
	
	long maximal=0,i,j,n,greutate, cost,G;
	f>>n; f>>G;
	for(j=1; j<=n; j++)
	{
		f>>greutate; f>>cost;
		for(i=maximal; i>=0; i--)
			if(i+greutate<=G)
				sol[i+greutate]=max(sol[i+greutate],cost+sol[i]);
			maximal=min(maximal+greutate,G);
	}
	maximal=0;
	for(i=0;i<=G; i++)
		if(maximal<sol[i])
			maximal=sol[i];
		g<<maximal;
	
	
}