#include <bits/stdc++.h>
using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
ifstream fin("rucsac.in");
ofstream fout("rucsac.out");

const int nmax = 5000;
const int gmax = 10000;
int n, W;
pair<int, int> a[nmax + 5];
pair<int, int> pref[nmax + 5];
bool chosen[nmax + 5];

int weight = 0;
int profit = 0;
int max_profit = -1;

// 2. euristica optimista - daca solutia curenta + solutia optimista pentru sufixul ramas
// tot e mai mica decat profixul maxim, nu are sensa sa continuam
inline bool viabil(int i) {
	return profit + pref[n].second - pref[i - 1].second > max_profit;
}

inline void take(int i) {
	weight += a[i].first;
	profit += a[i].second;
}

inline void untake(int i) {
	weight -= a[i].first;
	profit -= a[i].second;
}

void backtrack(int i) {
	if (i > n) {
		if (profit > max_profit) {
			max_profit = profit;
		}
		return;
	}
	if (!viabil(i)) {
		return;
	}
	// nu il luam
	backtrack(i + 1);
	// il luam
	take(i);
	if (weight <= W) { // 1. greutatea curenta nu trebuie sa depaseasca greutatea maxima
		backtrack(i + 1);
	}
	untake(i);
}

int main() {
	fin >> n >> W;
	for (int i = 1; i <= n; ++i) {
		fin >> a[i].first >> a[i].second;
	}
	// sortam dupa raportul p[i] / w[i] 
	sort(a + 1, a + n + 1, [&](const pair<int, int>& lhs, const pair<int, int>& rhs) {
		return lhs.second * rhs.first > rhs.second * lhs.first;
		});
	for (int i = 1; i <= n; ++i) {
		pref[i].first = pref[i - 1].first + a[i].first;
		pref[i].second = pref[i - 1].second + a[i].second;
	}
	// facem sume partiale pe w[] si p[]
	backtrack(1);
	fout << max_profit;
}