#include <fstream>
#include <iostream>
#include <set>
#include <bits/stdc++.h>

#define NMAX 5005

using namespace std;

//ifstream cin("rucsac.in");
//ofstream cout("rucsac.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;
long long startTime;

void bkt(int);
bool verif();
bool cmp(pair<int, int>, pair<int, int>);

long long getTime()
{
    return chrono::steady_clock::now().time_since_epoch().count();
}

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

    //sort ()

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

    bkt(1);

    cout <<pmax<<'\n';
    //cout.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];

     if((getTime()-startTime)/1000000 >= 199)
    {
        cout << pmax;
        exit(0);

    }
}

int greedy(int x, int g)
{

}

//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
*/