#include <fstream>
#include <algorithm>
#include <ctime>
#include <random>
using namespace std;
ifstream cin ("rucsac.in");
ofstream cout ("rucsac.out");
int n,k,r,s,g,sum[5010],g1,s1,lt,rt,mij,p,f[5010],op;
int long long s2,st[5010],dr[5010],x;
struct obiect
{
    int w,p;
    double b;
}a[5010];
bool ord (obiect a,obiect b)
{
    return a.b>b.b || (a.b==b.b && a.w<b.w);
}

void bkt (int l)
{
    for (int i=1; i>=0; i--)
    {
        if (i)
        {
            g=g+a[l].w;
            s=s+a[l].p;
        }
        if (g<=k && s+sum[l]>r)
        {
            g1=g;
            s1=s;
            for (int j=l+1; j<=n; j++)
            if (g1+a[j].w<=k) g1=g1+a[j].w,s1=s1+a[j].p;
            if (s1>r)
            {
                if (l<n) bkt(l+1);
                r=max(r,s);
            }
        }
        if (i)
        {
            g=g-a[l].w;
            s=s-a[l].p;
        }
    }

}
int main()
{
    mt19937 mt(time(NULL));
    cin>>n>>k;
    for (int i=1; i<=n; i++)
    {cin>>a[i].w>>a[i].p; a[i].b=a[i].p/a[i].w;}
    sort (a+1,a+n+1,ord);

    for (int i=n; i>=1; i--)
    {
        st[i]=s2;
        s2=s2+pow(2,n/(i*100));
        dr[i]=s2-1;
    }

        for (int t=1; t<=100; t++)
        {
            s=0;
            g=0;
            op=0;
            while (g<=k)
            {
                x=mt();
                x=x%1000000000000000ll;
                lt=1;
                rt=n;
                p=0;
                while (lt<=rt)
                {
                    mij=(lt+rt)/2;
                    if (st[mij]<=x && dr[mij]>=x) {p=mij; break;}
                    else if (st[mij]>x) rt=mij-1;
                    else lt=mij+1;
                }
                if (f[p]==0)
                {
                    g=g+a[p].w;
                    s=s+a[p].p;
                    f[p]=1;
                }
                op++;
                if (op>10000) break;
            }
            r=max(r,s);
            for (int i=1; i<=n; i++) f[i]=0;
        }

    s=g=0;
    for (int i=n; i>=1; i--)
    sum[i]=sum[i+1]+a[i].p;
    bkt(1);
    cout<<r;
    return 0;
}