#include <fstream>
using namespace std;
#define nmax 5002
#define pmax 10002
int T[nmax][pmax], g[nmax], p[nmax], n, Gmax;

int max(int a, int b) {
	if (a > b) {
		return a;
	}
	else
		return b;
}

int main() {
	ifstream fin("rucsac.in");
	ofstream fout("rucsac.out");
	fin >> n >> Gmax;
	for (int i = 1; i <= n; i++) {
		fin >> g[i] >> p[i];
	}

	for (int i = 0; i <= n; i++) {
		for (int j = 0; j <= Gmax; j++) {
			T[i][j] = 0;
		}
	}

	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= Gmax; j++) {
			if (g[i] > j || T[i - 1][j] >= T[i - 1][j - g[i]] + p[i]) {
				T[i][j] = T[i - 1][j];
			}
			else {
				T[i][j] = max(T[i - 1][j], T[i - 1][j - g[i]] + p[i]);
			}
		}
	}
	fout << T[n][Gmax] << endl;

	return 0;
}