#include <bits/stdc++.h>

int main() {
	int N, P;

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

	fin >> N >> P;
	std::vector<int> w;
	std::vector<int> p;

	w.resize(N + 1);
	p.resize(N + 1);

	for (int i = 1; i <= N; i++) {
		fin >> w[i] >> p[i];
	}

	std::vector<std::vector<int>> dp(N + 1, std::vector<int>(P + 1, 0));

	// dp[i][j] = profitul din primele i + 1 obiecte care au greutatea totala j
	//	



	for (int i = 1; i <= N; i++) {
			for (int j = P; j - w[i] >= 0; j--) {
				dp[i][j] = std::max(dp[i - 1][j], std::max(dp[i][j], dp[i - 1][j - w[i]] + p[i]));
			}	
	}

	
	fout << dp[N][P] << "\n";
	return 0;
}