#include <fstream>
using namespace std;
#define inf 0x3f3f3f
int sol[10005];
ifstream fin("rucsac.in");
ofstream fout("rucsac.out");
int main()
{
	int n, g, greutate,cost;
	fin>>n >>g;
	int maxim=0;
	while(n>0)
	{
		fin>>greutate >>cost;
		for(int i=maxim;i>=0;--i)
			if(sol[i]!=inf)
				if(i+greutate<=g)
					sol[i+greutate]=max(sol[i+greutate],cost+sol[i]);
		maxim=maxim+greutate;
		maxim=min(maxim,g);
		
		--n;
	}
	fout<<sol[g];		
			
	return 0;
}