#include <bits/stdc++.h>

using namespace std;

int n, g;
int w[5010], p[5010];
int sol[5010][10010];

int main() {

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

	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 = 1; j <= g; j++) {
			if (j >= w[i])
				sol[i][j] = max(sol[i-1][j-w[i]]+p[i], sol[i-1][j]);
			else
				sol[i][j] = sol[i-1][j];
		}
	}


	// for (int i = 0; i < n; i++) {
	// 	for (int j = 1; j <= g; j++) {
	// 		cout << sol[i][j] << "\t";
	// 		// sol[i][j] = max(sol[i-1][j-w[i]]+p[i], sol[i][j-1]);
	// 	}
	// 	cout << endl;
	// }

	cout << sol[n][g];

	return 0;
}