#include <iostream>
#include <fstream>

using namespace std;

int N, G, W[5000], P[5000];
bool seen[5000][10001];
int dp[5000][10001];
int go(int index, int weight) {
	if (index == N) {
		return 0;
	}
	if (seen[index][weight]) {
		return dp[index][weight];
	}
	seen[index][weight] = true;
	dp[index][weight] = go(index + 1, weight);
	if (W[index] <= weight) {
		dp[index][weight] = max(dp[index][weight], P[index] + go(index + 1, weight - W[index]));
	}
	return dp[index][weight];
}

int main() {
	ifstream cin("rucsac.in");
	ofstream cout("rucsac.out");
	cin >> N >> G;
	for (int i = 0; i < N; i++) {
		cin >> W[i] >> P[i];
	}
	cout << go(0, G) << endl;
	return 0;
}