#include <bits/stdc++.h>


#define MAX_P 50005

int main() {
	int N, P;

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

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

	// 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--) {
			dp[line][j] = dp[1 - line][j];
			if (j - W >= 0) {
				dp[line][j] = std::max(dp[line][j], dp[1 - line][j - W] + G);
			}
		}
		line = 1 - line;
	}

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