#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];

bool valid(int pos, int gr, int pr)
{
    return ((gr<=G) && (pr+Sp[pos]>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]=0;
    bkt(pos+1,gr,pr);
    v[pos]=1;
    bkt(pos+1,gr+obj[pos].w,pr+obj[pos].p);
}

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=1; i<=N; i++)
        fout<<obj[i].w<<' '<<obj[i].p<<'\n';

    for(i=1; i<=N; 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;
}