#include <iostream>
#include <fstream>
using namespace std;

ifstream fin("rucsac.in");
ofstream fout("rucsac.out");

int g[5001], p[5001], ap[10001], au[10001];

int main() {
	int N, G, max = 0, max_i;

	au[0] = -1;
	fin >> N >> G;
	for (int i = 1; i <= N; i++) {
		fin >> g[i] >> p[i];
		for (int j = G - g[i]; j >= 0; j--) {
			if (au[j] != 0) {
				int p1 = ap[j] + p[i];
				int k = j + g[i];

				if (ap[k] < p1) {
					ap[k] = p1;
					au[k] = i;
				}

				if (p1 > max) {
					max = p1;
					max_i = k;
				}
			}
		}
	}

	fout << max;
	/*int k = max_i;
	while (k > 0) {
		int i = au[k];
		cout << i << ":" << p[i] << "\n";
		k -= g[i];
	}*/

	return 0;
}