#include <fstream>
//#include <conio.h>
using namespace std;
#define nmax 5002
#define pmax 10002
int T[2][pmax], g[nmax], p[nmax], n, Gmax, k;

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 <= 1; i++) {
		for (int j = 0; j <= Gmax; j++) {
			T[i][j] = 0;
		}
	}   */
	k = 0;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= Gmax; j++) {
			if (g[i] > j || T[1-k][j] >= T[1-k][j - g[i]] + p[i]) {
				T[k][j] = T[1-k][j];
			}
			else {
				T[k][j] = max(T[1-k][j], T[1-k][j - g[i]] + p[i]);
			}
		}
		k=1-k;
	}
	fout << max(T[1][Gmax],T[0][Gmax]) << endl;

	return 0;
}