#include <fstream>
using namespace std;
int cost[5005],castig[5005],gmax[10010];
int main()
{
	ifstream f("rucsac.in");
	ofstream g("rucsac.out");
	int N,i,j,G;
	f>>N>>G;
	for(i=1;i<=N;i++)
	{	f>>cost[i]>>castig[i];}
	for(i=1;i<=N;i++)
	{	for(j=G-cost[i];j>=0;j--)
		 { if(gmax[j+cost[i]]<gmax[j]+castig[i])
			  { gmax[j+cost[i]]=gmax[j]+castig[i];}
		 }
	}
	g<<gmax[G];
	f.close();
	g.close();
	return 0;
}