#include<fstream>
using namespace std;

int main(){

	ifstream fin("rucsac.in");
	ofstream fout("rucsac.out");

	int d[10000], w[5000], p[5000], i, j, n, g, max;

	fin >> n >> g;
	for(i=0; i<n; i++) fin >> w[i] >> p[i];
	d[0] = 0;
	max = 0;
	for(i=1; i<=g; i++) d[i] = -1;
	
	for(i=0; i<n; i++) {
		for(j=g; j>=w[i]; j--){
			if(d[j - w[i]]!= -1 && d[j-w[i]]+p[i] > d[j]) d[j] = d[j-w[i]]+ p[i];
			if(d[j] > max) max = d[j];
		}
	}
	
	fout << max;
	
	return 0;
}