#include <bits/stdc++.h>

#define BUFFER_SIZE 1 << 17
#define NMAX 5005
#define GMAX 10005

char BUFFER[BUFFER_SIZE];
int pos = BUFFER_SIZE;
int w[NMAX], p[NMAX];
int dp[2][GMAX];

char next() {
	if (pos == BUFFER_SIZE) {
		fread(BUFFER, 1, BUFFER_SIZE, stdin);
		pos = 0;
	}

	return BUFFER[pos++];
}

inline int read() {
	int n = 0;
	char c = next();

	while (!('0' <= c && c <= '9')) {
		c = next();
	}

	while ('0' <= c && c <= '9') {
		n = (n << 3) + (n << 1) + (c - '0');
		c = next();
	}

	return n;
}

int main() {
	freopen("rucsac.in", "r", stdin);
	freopen("rucsac.out", "w", stdout);

	int n = read(), g = read();
	for (int i = 1 ; i <= n ; ++i) {
		w[i] = read(), p[i] = read();
	}

	int l = 0;
	for (int i = 1 ; i <= n ; ++i, l = 1 - l) {
		for (int cap = 0 ; cap <= g; ++cap) {
			dp[1 - l][cap] = dp[l][cap];

			if (w[i] <= cap) {
				dp[1 - l][cap] = std::max(dp[1-l][cap], dp[l][cap - w[i]] + p[i]);
			}
		}
	}

	printf("%d\n", dp[l][g]);
	return 0;
}