#include <fstream>
#include <vector>
#include <algorithm>
#include <cstdlib>
#include <ctime>

using namespace std;
ifstream fin("rucsac.in");
ofstream fout("rucsac.out");

typedef double ld;

int n, wmax, pmax, ww, pp;
pair<int, int> a[5005];
vector<pair<int, int>> v;

bool cmp(pair<int, int> a, pair<int, int> b)
{
  ld p1=ld(a.second/a.first), p2=ld(b.second/b.first);
  return p1>p2;
}

/*bool verif()
{
  int i;
  for(i=1; i<=n; i++)
  {
    if(v[i])
    {
      ww+=w[i];
      pp+=p[i];
    }
  }
  if(ww<W) return true;
  return false;
}*/

//poti calcula separat pt ultime 15/20 pozitii si sa te opresti

ld greedy(int poz, int wmax, bool inc)
{
  ld pp=0, ww=0; v.clear();
  for(int i=poz; i<=n; i++) v.push_back(a[i]);
  //sort(v.begin(), v.end(), cmp);
  for(auto i:v)
  {
    //fout<<i.first<<' '<<i.second<<'\n';
    if(ww+i.first<=wmax)
    {
      ww+=i.first;
      pp+=ld(i.second);
    }
    else if(!inc)
    {
      ld p=i.second/i.first;
      pp=ld(pp+ld(p*(wmax-ww)));
      break;
    }
  }
  //fout<<wmax<<' '<<inc<<' '<<pp<<"\n\n\n\n";
  return pp;
}

void bkt(int poz)
{
  if(ww>wmax) return;
  pmax=max(pmax, pp);
  if(ld(pp+greedy(poz, wmax-ww, 0))<=pmax) return;
  //if(nu exista i a.i. sw[i]<ww<sw[i+1] si p[i]<ptot) return;
  if(poz<=n)
  {
    bkt(poz+1);
    ww+=a[poz].first;
    pp+=a[poz].second;
    bkt(poz+1);
    ww-=a[poz].first;
    pp-=a[poz].second;
  }
  return;
}

int main()
{
  int i, j, pp=0, ww=0, val;
  val=1e5;
  srand(time(0));
  fin>>n>>wmax;
  for(i=1; i<=n; i++) fin>>a[i].first>>a[i].second;
  for(i=1; i<=val; i++)
  {
    random_shuffle(a+1, a+n+1);
    for(ww=pp=0, j=1; j<=n; j++)
    {
      if(ww+a[j].first<=wmax)
      {
        ww+=a[j].first;
        pp+=a[j].second;
      }
    }
    pmax=max(pmax, pp);
  }
  sort(a+1, a+n+1, cmp);
  pmax=greedy(1, wmax, 1);
  bkt(1);
  fout<<pmax<<'\n';
}