#include <bits/stdc++.h>

int main() {
	int N, P;

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

	fin >> N >> P;
	int dp[2][50001];

	// dp[i][j] = profitul din primele i obiecte care au greutatea totala ji - 1
	int line = 0;
	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[line][j] = std::max(dp[1 - line][j], std::max(dp[line][j], dp[1 - line][j - W] + G));
			} else {
				dp[line][j] = std::max(dp[1 - line][j], dp[line][j]);
			}
		}
		line = 1 - line;
	}


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