#include <iostream>
#include <fstream>
#include <algorithm>

#define NMAX 5005
#define GMAX 10005
using namespace std;

int w[NMAX], p[NMAX];
int optimum[GMAX];

int main() {

	ifstream cin("rucsac.in");
	ofstream cout("rucsac.out");
	
	int n, g;
	cin >> n >> g;

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

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

	cout << optimum[g] << '\n';
	return 0;
}