#include <fstream>

struct elem {
	int wgh, cost;
};

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

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