#include <fstream>

using namespace std;

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

int max(int a, int b) {
	return (a > b) ? a : b;
}

int v[5010], g[5010], N, G, rucsac[10010];

int main() {
	ios_base::sync_with_stdio(false);
	in.tie(NULL), out.tie(NULL);

	in >> N >> G;
	for (int i = 0; i < N; i++) {
		in >> g[i] >> v[i];
		for (int j = G - g[i]; j >= 0; j--) {
			rucsac[j + g[i]] = max(rucsac[j + g[i]], rucsac[j] + v[i]);
		}
	}
	out << rucsac[G];
}