#include <fstream>
using namespace std;

typedef struct obj
{
	int p, w;
};

int v[10001], n, g;
obj o[5001];
const int mINF=-1000000000;

void init()
{
	for(int i=1;i<=g;i++)
		v[i]=mINF;
}

int main()
{
	int i, j;
	
	ifstream in("rucsac.in");
	ofstream out("rucsac.out");
	
	in>>n>>g;
	for(i=0;i<n;i++)
		in>>o[i].w>>o[i].p;
	
	for(i=0;i<n;i++)
		for(j=g-o[i].w;j>=0;j--)
			if(v[j]!=mINF && v[j]+o[i].p>v[j+o[i].w])
				v[j+o[i].w]=v[j]+o[i].p;
	
	for(i=g;v[i]==mINF;i--) 
		continue;
	
	out<<v[i];
	
	in.close();
	out.close();
	
	return 0;
}