#include <fstream>
#include <cstdlib>
#include <iostream>
#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;
	//freopen("rucsac.in","r",stdin);
	//freopen("rucsac.out","w",stdout);
	//ifstream f("rucsac.in");
	FILE *f = fopen("rucsac.in", "rt");
	FILE *gout = fopen("rucsac.out", "wt");
	fscanf(f, "%d%d", &n, &g);
	for(i = 0; i < n; ++i) {
		fscanf(f, "%d%d", &w[i], &p[i]);
		//cin >> 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]);
	}
	//cout << ans << endl;
	fprintf(gout, "%d\n", ans);
	fclose(f);
	fclose(gout);
	//gout.close();
	return 0;
}