#include <iostream>
#include <algorithm>
using namespace std;

#define N 14000
int m[1000][1000];

void Knapsack(int *v, int *w, int c, int n) {

	int jMax = min(w[n] - 1, c);
	for (int j = 0; j <= jMax; j++) m[n][j] = 0;
	for (int j = w[n]; j <= c; j++) m[n][j] = v[n];
	for (int i = n - 1; i > 1; i--) {
		int jMax = min(w[n] - 1, c);
		for (int j = 0; j <= jMax; j++) m[i][j] = m[i+1][j];

		for (int j = w[n]; j <= c; j++) m[i][j] = max(m[i+1][j],m[i+1][j-w[i]]+v[i]);


	}
	m[1][c] = m[2][c];

	if (c >= w[1])m[1][c] = max(m[1][c], m[2][c - w[1]] + v[1]);
	
	cout << m[1][c]<<endl;


}

int main() {
	int c, n;
	int w[N];
	int v[N];

	cin >> n >> c;
	for (int i = 1; i <= n; i++) cin >> w[i] >> v[i];
	Knapsack(v, w, c, n);

	return 0;
}