#include <fstream>
using namespace std;
int w[5001],p[5001],n,g,i,j,b[2][10001],l;
int main() {
	ifstream f("rucsac.in");
	ofstream go("rucsac.out");
	f>>n>>g;
	for (i=1; i<=n; i++) 
		f>>w[i]>>p[i];
	l=1;
	for (i=1; i<=n; i++, l=1-l) 
		for (j=1; j<=g; j++) {
			b[1-l][j]=b[l][j];
			if (j>=w[i])
				b[1-l][j]=max(b[1-l][j],b[l][j-w[i]]+p[i]);
		}
	if (n%2)
		l=0;
	else l=1;
	go<<b[l][g]<<'\n';
	go.close();
	return 0;
}