#include<cstdio>
#include<ctime>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=5000;
const int G=10000;
const int GEN_SIZE=64;
const int SQRT_GEN_SIZE=8;
const int LOG_GEN_SIZE=6;
const int TIME=1000000;
class Object{
    public:
        int w,p;
};
int n,g;
Object v[N+1];
int maxx=0;
class Individual{
    public:
        int s[N/32+1];
        int fit;
        int ok;
        Individual(){
            memset(s,0,sizeof(s));
            fit=0;
            ok=0;
        }
        void set_fit(){
            for(int i=0;i<n;i++)
                if(s[i/32]&(1<<(i%32))){
                    fit+=v[i+1].p;
                    ok+=v[i+1].w;
                }
            if(ok<=g)
                maxx=max(maxx,fit);
        }
        bool operator<(const Individual&i)const{
            if(ok<=g&&i.ok<=g)
                if(fit==i.fit)
                    return ok<i.ok;
                else
                    return fit>i.fit;
            else if(ok<=g)
                return true;
            else if(i.ok<=g)
                return false;
            else
                return 1LL*(ok-g)*(i.fit-maxx)<1LL*(i.ok-g)*(fit-maxx);
        }
};
Individual gens[GEN_SIZE+1];
Individual gens2[GEN_SIZE+1];
Individual comb(Individual i1,Individual i2){
    Individual res;
    for(int i=0;i<n;i++){
        int p1=i1.s[i/32]&(1<<(i%32));
        int p2=i2.s[i/32]&(1<<(i%32));
        if(p1+p2==1)
            res.s[i/32]+=(rand()%2)<<(i%32);
        else
            res.s[i/32]+=((p1+p2)/2)<<(i%32);
    }
    res.set_fit();
    return res;
}
int aprox(double x){
    int a=x;
    if(a==0)
        return 1;
    return a;
}
void init(){
    int totalW;
    for(int i=1;i<=n;i++)
        totalW+=v[i].w;
    int med=aprox(1.0*g/totalW*n);
    for(int i=1;i<=GEN_SIZE;i++)
        for(int j=0;j<n;j++){
            int a=rand()%n;
            if(a<med)
                gens[i].s[j/32]+=1<<(j%32);
        }
    for(int i=1;i<=GEN_SIZE;i++)
        gens[i].set_fit();
}
void genetic_algorithm(){
    init();
    sort(gens+1,gens+GEN_SIZE+1);
    int turns=TIME/n/GEN_SIZE;
    while(turns--){
        for(int i=1;i<=SQRT_GEN_SIZE;i++)
            gens2[i]=gens[1];
        int k=SQRT_GEN_SIZE;
        for(int i=1;i<=SQRT_GEN_SIZE;i++)
            for(int j=1;j<=SQRT_GEN_SIZE;j++)
                if(i!=j)
                    gens2[++k]=comb(gens[i],gens[j]);
        for(int i=1;i<=GEN_SIZE;i++)
            gens[i]=gens2[i];
        sort(gens+1,gens+GEN_SIZE+1);
    }
}
int main(){
    srand(time(NULL));
    freopen("rucsac.in","r",stdin);
    freopen("rucsac.out","w",stdout);
    scanf("%d%d",&n,&g);
    for(int i=1;i<=n;i++)
        scanf("%d%d",&v[i].w,&v[i].p);
    genetic_algorithm();
    printf("%d",maxx);
    return 0;
}