#include <iostream>
#include <fstream>

using namespace std;

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

int n,g;
int smax;

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

obiect obiecte[5000];

void recursiv(int k, int gc, int pc) {
    int tgc=gc+obiecte[k].greutate;
    int tpc=pc+obiecte[k].val;

    bool nultim=k<n-1;
    k++;
    if(tgc<=g) {
        if(tpc>smax)
            smax=tpc;
        if(tgc<g && nultim)
            recursiv(k,tgc,tpc);
    }
    if(nultim)
        recursiv(k,gc,pc);

}

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

    recursiv(0,0,0);

    fout<<smax;

    return 0;
}