#include <fstream>

using namespace std;

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

int p[5005], w[5005], pr[10005];
bool f[10005];

int main() {
	int n, g;
	cin >> n >> g;
	for (int i = 1; i <= n; i++) {
		cin >> w[i] >> p[i];
	}
	f[0] = true;
	for (int i = 1; i <= n; i++) {
		for (int j = g - w[i]; j >= 0; j--) {
			if (f[j] == true) {
				f[j + w[i]] = true;
				if (pr[j + w[i]] < pr[j] + p[i]) {
					pr[j + w[i]] = pr[j] + p[i];
				}
			}
		}
	}
	int ans = 0;
	for (int i = 1; i <= 10000; i++) {
		ans = max(ans, pr[i]);
	}
	cout << ans;
	return 0;
}