#include<fstream>
#include<string.h>
#include<algorithm>
using namespace std;
int w[5001], p[5001];
int o[10001];
int sol;
int n,g,i,j;
int main() 
{
	ifstream fi("rucsac.in");
	ofstream fo("rucsac.out");
	fi>>n>>g;
	for (i=1;i<=n;i++)	fi>>w[i]>>p[i];
	o[0]=0;
	for(i=1;i<=n;i++)
		for(j=g-w[i];j>=0;j--) 
		{
			if(o[j+w[i]]<o[j]+p[i])
			{
				o[j+w[i]]=o[j]+p[i];
				if(o[j+w[i]]>sol)
					sol=o[j+w[i]];
			}
		}
	fo<<sol;
	fi.close();
	fo.close();
	return 0;
}