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

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

int n, g, w[5005], p[5005], d[2][10005];


int main() {

	fin >> n;
	fin >> g;
	for (int i = 1; i <= n; ++i) {
		fin >> w[i] >> p[i];
	}
	
	for (int i = 1; i <= n; ++i) {
		for (int j = 1; j <= g; ++j) {
			if (w[i] <= j) {
				d[i%2][j] = max(d[(i - 1)%2][j], d[(i - 1)%2][j - w[i]] + p[i]);
			}
			else d[i%2][j] = d[(i - 1)%2][j];
		}
	}

	fout << d[n % 2][g];



	return 0;
}