#include <fstream>
#include <cstring>

using namespace std;

static const int MAXN = 5009, MAXG = 10009;
int w[MAXN], p[MAXN];
int max_val[MAXG];

int main() {
	int i, n, g, lm, j;
	ifstream f("rucsac.in");
	f >> n >> g;
	for(i = 0; i < n; ++i) {
		f >> w[i] >> p[i];
	}
	f.close();
	memset(max_val, -1, sizeof(max_val));
	max_val[0] = 0;
	lm = 0;
	for(i = 0; i < n; i++) {
		int wi, pi;
		wi = w[i]; pi = p[i];
		for(j = min(lm, g - wi); j >= 0; j--) {
			int temp = max_val[j];
			if(temp > -1 && max_val[j + wi] < temp + pi) {
				max_val[j + wi] = temp + pi;
				lm = max(lm, j + wi);
			}
		}
	}
	int ans = 0;
	ofstream gout("rucsac.out");
	for(i = 0; i <= g; ++i) {
		ans = max(ans, max_val[i]);
	}
	gout << ans << endl;
	gout.close();
	return 0;
}