#include <fstream>
#include <cmath>

struct elem {
	int wgh;
	int val;
};

int dp[5005][10005];
elem vec[5005];

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