#include <bits/stdc++.h>
#define NMAX 10005

using namespace std;

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

int N,G;
int v[NMAX],Pmax,Sp[NMAX],minw[NMAX];

struct obiect
{
    int w,p;
}obj[NMAX];

int greedy(int pos, int gr, int pr)
{
    int i,gtotal=gr,ptotal=pr;

    for(i=pos; i<=N && gtotal<=G; i++)
        if(obj[i].w+gtotal<=G)
        {
            gtotal+=obj[i].w;
            ptotal+=obj[i].p;
        }

    return ptotal;
}

bool valid(int pos, int gr, int pr)
{
    return ((gr<=G) && (minw[pos]+gr<=G) && (pr+Sp[pos]>=Pmax) && (greedy(pos,gr,pr)>=Pmax));
}

void bkt(int pos, int gr, int pr)
{
    if(!valid(pos,gr,pr)) return;

    if(pos==N+1)
    {
        if(pr>Pmax)
            Pmax=pr;
        return;
    }

    v[pos]=1;
    bkt(pos+1,gr+obj[pos].w,pr+obj[pos].p);

    v[pos]=0;
    bkt(pos+1,gr,pr);
}

bool cmp(obiect a, obiect b)
{
    return (a.p*b.w > b.p*a.w);
}

int main()
{
    int i;

    fin>>N>>G;

    for(i=1; i<=N; i++)
        fin>>obj[i].w>>obj[i].p;

    sort(obj+1,obj+N+1,cmp);

    for(i=N; i>=1; i--)
        Sp[i]=Sp[i+1]+obj[i].p;

    minw[N]=obj[N].w;
    for(i=N-1; i>=1; i--)
        minw[i]=min(minw[i+1],obj[i].w);

    bkt(1,0,0);

    fout<<Pmax;

    return 0;
}