#include<fstream>
#define e endl
#define FOR(a,b,c) for(int a=(b); a<(c); ++a)
#define TO(a,b) for(int a=0; a<(b); ++a)
using namespace std;

					fstream f("rucsac.in");
					ofstream t("rucsac.out");
					
													int N, G, S;
													int W[5001], P[5001], Q[10001];
int main(){
	
	f>>N>>G;
	// N- Numarul de obiecte
	// G- Greutatea maxima
	// W1- Greutatea obiectului i
	// P1- Profitul obiectului i 
	
	for(int i=1; i<=N; ++i){
		f>>W[i]>>P[i];
	}
	
	Q[0]=0;
	S=0;
	
	for(int i=1; i<=N; ++i)
		for(int j=G - W[i]; j>=0; --j){
			if(Q[j+W[i]] < Q[j]+P[i]){
				Q[j+W[i]] = Q[j] +P[i];
				if(Q[j+W[i]] > S) 
					S = Q[j+W[i]];
			}
		}
	t<<S;
	
	return 0;
}