#include <iostream>
#include <fstream>

#define NMAX 5000
#define GMAX 10001
#define max(a,b) ((a) > (b))?(a):(b)

const char IN[] = "rucsac.in", OUT[] = "rucsac.out";

using namespace std;

int N, G;
int v[NMAX];
int W[NMAX];
int best[GMAX];

inline void readData() {
	freopen(IN, "r", stdin);
	scanf("%d %d", &N, &G);
	for (int i = 0; i < N; ++i) {
		scanf(" %d %d", &W[i], &v[i]);
	}
	fclose(stdin);
}

int ksp() {
	for (int i = 0; i < N; ++i) {
		for (int w = G; w >= W[i]; --w) {
			best[w] = max(best[w], best[w - W[i]] + v[i]);
		}
	}
	return best[G];
}

int main() {
	readData();
	int r = ksp();
	freopen(OUT, "w", stdout);
	printf("%d\n", r);
	fclose(stdout);
	return 0;
}