#include <bits/stdc++.h>
using namespace std;

int main() {
	int n, G;
	cin >> n >> G;

	int w[5001], p[5001];
	for (int i = 0; i < n; i++) {
		cin >> w[i] >> p[i];
	}

	long long dp[10001] = {0};

	for (int i = 0; i < n; i++) {
		for (int j = G; j >= w[i]; j--) {
			dp[j] = max(dp[j], dp[j - w[i]] + p[i]);
		}
	}

	cout << dp[G] << "\n";

	return 0;
}