#include <fstream>
#include <cmath>

int dp[2][10005];

int main () {
	std::ifstream fin("rucsac.in");
	std::ofstream fout("rucsac.out");
	int nrn, nrg;
	int wgh, val;
	fin >> nrn >> nrg;
	for (int index = 1; index <= nrn; index++) {
		fin >> wgh >> val;
		for (int index2 = 0; index2 <= nrg; index2++) {
			if (index2 >= wgh) {
				dp[index & 1][index2] = std::max(dp[1 - (index & 1)][index2], dp[1 - (index & 1)][index2 - wgh] + val);
			}
			else {
				dp[index & 1][index2] = dp[1 - (index & 1)][index2];
			}
		}
	}
	fout << dp[nrn & 1][nrg];
	return 0;
}