#include <bits/stdc++.h>
#define int long long
using namespace std;

constexpr int N = 500010, K = 1010, M = 10010;
int n, m, f[K][M], ans, v[N], w[N];

void dp() {
	for (int i = 1; i <= n; i++) {
		for (int j = 0; j <= m; j++) {
			if (j < w[i]) f[i][j] = f[i-1][j];
			else f[i][j] = max(f[i-1][j], f[i-1][j-w[i]] + v[i]);
		}
	}
	ans = f[n][m];
	return;
}

signed main() {
	freopen("Mining.in", "r", stdin);
	freopen("Mining.out", "w", stdout);
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	cin >> n >> m;
	for (int i = 1; i <= n; i++) cin >> v[i] >> w[i];
	if (n <= 1000) dp();
	else {
		int flg = 1;
		for (int i = 1; i < n; i++) {
			if (w[i] != w[i+1]) {
				flg = 0;
				break;
			}
		}
		if (flg) {
			sort(v+1, v+1+n);
			for (int i = 1; i <= m / w[1]; i++) ans += v[n-i+1];
		} else {
			ans = 1;
		}
	}
	cout << ans;
	return 0;
}