#include <bits/stdc++.h>

int main() {
	int N, P;

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

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

	// dp[i][j] = profitul din primele i obiecte care au greutatea totala j
	for (int i = 1; i <= N; i++) {
		int W, G;
		fin >> W >> G;
		for (int j = P; j >= 0; j--) {
			if (j - W >= 0) {
				dp[i][j] = std::max(dp[i - 1][j], std::max(dp[i][j], dp[i - 1][j - W] + G));
			} else {
				dp[i][j] = std::max(dp[i - 1][j], dp[i][j]);
			}
		}
	}


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