#include <fstream>
#include <cmath>

struct elem {
	int wgh;
	int val;
};

elem vec[5005];

int nrn;

int solve (int pos, int wLeft) {
	if (pos == nrn) {
		return 0;
	}
	else {
		int ans = solve(pos + 1, wLeft);
		if (wLeft >= vec[pos].wgh) {
			ans = std::max(ans, solve(pos + 1, wLeft - vec[pos].wgh) + vec[pos].val);
		}
		return ans;
	}
}

int main () {
	std::ifstream fin("rucsac.in");
	std::ofstream fout("rucsac.out");
	int nrg;
	fin >> nrn >> nrg;
	for (int index = 0; index < nrn; index++) {
		fin >> vec[index].wgh >> vec[index].val;
	}
	fout << solve(0, nrg);
	return 0;
}