#include <iostream>
#include <fstream>

using namespace std;

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

int n,g;
bool x[5000];
int smax;

typedef struct obiect_t{
    int val;
    int greutate;
}obiect;

obiect obiecte[5000];

typedef struct calc_res_t{
    int p;
    int g;
}calc_res;

calc_res calc(int k){
    calc_res r;
    r.g=0;
    r.p=0;
    for(int i=0;i<=k;i++){
        if(x[i]){
            r.g+=obiecte[i].greutate;
            r.p+=obiecte[i].val;
        }
    }
    return r;
}

void recursiv(int k){
    for(int i=0;i<=1;i++){
        x[k]=i==1;
        calc_res r=calc(k);
        if(r.g<=g){
            if(r.p>smax)
                smax=r.p;
            if(r.g<g && k<n-1)
                recursiv(k+1);
        }
    }
}

int main()
{
    fin>>n>>g;
    for(int i=0;i<n;i++)
        fin>>obiecte[i].greutate>>obiecte[i].val;

    recursiv(0);

    fout<<smax;

    return 0;
}