#include <bits/stdc++.h>

using namespace std;

const int Nmax = 5001, Gmax = 10001;

int n, g;
int weights[Nmax], values[Nmax];
int dp[Gmax]; // valoarea maxima obtinuta din maxim greutatea i

int main() {
	freopen("rucsac.in", "r", stdin);
	freopen("rucsac.out", "w", stdout);
	ios::sync_with_stdio(false);
	cin.tie(0);
	
	cin >> n >> g;
	for (int i = 1; i <= n; ++i) {
		cin >> weights[i] >> values[i];
	}

	for (int i = 1; i <= n; ++i) {
		for (int w = g; w >= 1; --w) {
			if (w - weights[i] >= 0) {
				dp[w] = max(dp[w], dp[w - weights[i]] + values[i]);
			}
		}
	}

	cout << dp[g];

	return 0;
}