#include<fstream>
#include<algorithm>
#define N 5050

using namespace std;

ifstream f("rucsac.in");
ofstream out("rucsac.out");

int g[N],p[N],v[N],n, gmax, pmax, smg, smp;

void bkt(int k)
{
    if(k>n)
    {
        if(smp > pmax)
            pmax = smp;
        return;
    }

    if(smg +g[k] <= gmax)
    {
        smg += g[k];
        smp += p[k];
        v[k] = 1;
        bkt(k+1);
        v[k] = 0;
        smp -= p[k];
        smg -= g[k];
    }
    v[k] = 0;
    bkt(k+1);
}

int main()
{
    f>>n>>gmax;

    for(int i  =1; i<=n; ++i)
    {
        f>>g[i]>>p[i];
    }

    bkt(1);

    out<<pmax;
}