#include <fstream>
#include <vector>

using namespace std;

ifstream f("rucsac.in");
ofstream g("rucsac.out");

int main() {
	int n, weight;

	f >> n >> weight;

	vector<int> w(n + 1), p(n + 1);
	for (int i = 1; i <= n; i++) {
		f >> w[i] >> p[i];
	}

	vector<vector<int>> dp(2, vector<int>(weight + 1, 0));
	// dp[i][j] = profitul maxim obtinut din primele i obiecte cu greutatea totala cel mult j

	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= weight; j++) {
			if (w[i] > j) {
				dp[1][j] = dp[0][j];
			} else {
				dp[1][j] = max(dp[0][j], dp[0][j - w[i]] + p[i]);
			}
		}
		for (int j = 1; j <= weight; j++) {
			dp[0][j] = dp[1][j];
		}
	}

	g << dp[1][weight];

	f.close();
	g.close();
	return 0;
}