#include      <iostream>
#include      <fstream>
#include      <algorithm>

using namespace std;

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

int v[5000], w[5000], n, W;
int mat[5000][5000]; 

int kn(int n, int c) {
	if (mat[n][c]) return mat[n][c];
	else {
		if (n == 0 || c == 0) mat[n][c] = -1;
		else {
			if (w[n] > c) kn(n - 1, c);
			else {
				int case1 = kn(n - 1, c);
				int case2 = v[n] + kn(n - 1, c - w[n]);
				mat[n][c] = max(case1, case2);
			}
		}
	}

}

int main() {

	ios_base::sync_with_stdio(false);
	in.tie(NULL); out.tie(NULL);

	in >> n >> W;
	v[0] = 0;
	for (int i = 1; i <= n; i++)in >> w[i] >> v[i];
	out << kn(n, W);

}