#include <fstream>
#include <iostream>
#include <set>

#define NMAX 5005

using namespace std;

ifstream fin("bktop.in");
ofstream fout("bktop.out");

int n, W;
int p[NMAX], w[NMAX];
int crtw, crtp;
int sumap[NMAX];
int pmax;
bool v[NMAX];
int i, j;
set<pair<int, int>> s;

void bkt(int);
bool verif();

int main()
{
    fin >>n>>W;
    for (i = 1; i <= n; ++i)
        fin >>w[i]>>p[i];

    for (i = n; i >= 1; --i)
        sumap[i] = sumap[i+1] + p[i];

    bkt(1);

    fout <<pmax<<'\n';
    fout.close();
    return 0;
}

void bkt(int pos)
{
    if (pos == n+1)
    {
        if (crtw <= W) //weight <= m
            pmax = max(pmax, crtp);
        return;
    }

    v[pos] = 0;
    bkt(pos+1);

    crtw += w[pos];
    crtp += p[pos];
    v[pos] = 1;
    set<pair<int, int>>::iterator it = s.insert({crtw, crtp}).first;
    if (crtw > W || crtp + sumap[pos+1] <= pmax || (s.size() > 1 && (*(prev(it))).second >= crtp))
    {
        ;
    }
    else
        bkt(pos+1);
    //also, nu exista i a.i. sw[i] < sumw < sw[i+1] si pw[i] < sumap
    //also, sumap + greedy(i+1, w - sumap) <= pmax

    s.erase({crtw, crtp});
    crtw -= w[pos];
    crtp -= p[pos];
}
//putem precalcula pentru ultimele 15-20 poz
/*
void bkt(int pos)
{
    if (pos == n+1)
    {
        if (crtw <= W) //weight <= m
            pmax = max(pmax, crtw);
        return;
    }

    v[pos] = 0;
    bkt(pos+1);

    crtw += w[i];
    crtw += p[i];
    v[pos] = 1;
    if (crtw > W || crtp + suma[pos+1])
        return;
    //also, nu exista i a.i. sw[i] < sumw < sw[i+1] si pw[i] < sumap
    //also, sumap + greedy(i+1, w - sumap) <= pmax
    else
        bkt(pos+1);
    crtw -= w[i];
    crtw -= p[i];
}
//putem precalcula pentru ultimele 15-20 poz
*/