#include <bits/stdc++.h>

using namespace std;

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

const int nmax = 5005;
int n,W;
struct ob{
int w,p;
}v[nmax];

int pmax;
int p,w;

int sp[nmax];

bool cmp(ob a, ob b)
{
    return ((a.p/a.w) == (b.p/b.w)) ? (a.w>b.w) : ((a.p/a.w) > (b.p/b.w));
}

void cancel(int i)
{
    w -= v[i].w;
    p -= v[i].p;
}

long long startTime;

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

void bkt(int i)
{
    if((getTime()-startTime)/1000000 >= 195)
    {
        fout << pmax;
        exit(0);
    }
    if(i==n+1)
    {
        pmax = max(pmax,p);
        return;
    }

    bkt(i+1);

    w += v[i].w;
    p += v[i].p;

    if(w>W)
    {
        cancel(i);
        return;
    }
    else if(p + sp[i+1] <= pmax)
    {
        cancel(i);
        return;
    }
    bkt(i+1);
    cancel(i);
}

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

    sort(v+1,v+n+1,cmp);

    int crt = 0, pi = 1;
    while(crt <= W)
    {
        crt += v[pi].w;
        if(crt <= W)
            pmax += v[pi].p;
        ++pi;
    }

    for(int i=n ; i>=1 ; --i)
        sp[i] = sp[i+1] + v[i].p;

    bkt(0);
    fout << pmax;

    return 0;
}