#include<string.h>
#include<fstream>

using namespace std;

int W[5001], P[5001],Optim[10001],n,g,i,sol,j;

int main() {

	ifstream in("rucsac.in");
	ofstream out("rucsac.out");
	in>>n>>g;

	for ( i = 1; i <= n; ++i) {
		in>>W[i]>>P[i];
	}

	for( i = 1; i <= n; ++i)
		for( j = g - W[i]; j >= 0; --j) {
			if( Optim[j+W[i]] < Optim[j] + P[i] )
			{
				Optim[j+W[i]] = Optim[j] + P[i];
				if( Optim[j+W[i]] > sol)
					sol = Optim[j+W[i]];
			}
		}
	out<<sol;
	return 0;
}