#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;
ifstream cin("rucsac.in");
ofstream cout("rucsac.out");
int n, g;
int v[5001];
int bestprof = -1;
int rest[5001];
int ales[5001];
struct obiect
{
	int gr;
	int v;
	bool operator >	(const obiect x) const
	{
		return ((this->v * x.gr) < (x.v*this->gr));
	}
	bool operator < (const obiect x) const
	{
		return ((this->v * x.gr) >(x.v * this->gr));
	}
};
int ginit = 0;
int profinit = 0;
vector <obiect>o;
void bkt(int level)
{
    bestprof = max(profinit, bestprof);
	if (level > n || ginit==g )
	{
		;
	}
	else
	{
		if (profinit + rest[level]> bestprof)
		{
			if (ginit+o[level].gr<=g)
			{
			    ginit+=o[level].gr;
				profinit+=o[level].v;
				bkt(level + 1);
				ginit -= o[level].gr;
				profinit-=o[level].v;
			}
			bkt(level+1);
		}
	}

}
int main()
{
	cin >> n >> g;
	for (int i = 0; i < n; i++)
	{
		int gr, v;
			cin >> gr >> v;
			o.push_back({ gr,v});
	}
	sort(o.begin(),o.end());
    
	rest[n]=0;
	for (int i = n - 1; i >= 0; i--)
	{
		rest[i] = rest[i + 1] + o[i].v;
	}
	bkt(0);
	cout << bestprof;
	
}