#include <iostream>
#include <fstream>
using namespace std;
ifstream fin("rucsac.in");
ofstream fout("rucsac.out");

int N,G,X[5000],Max;

struct Product
{
    int W,P;
};

Product V[10005];

void Read()
{
    fin>>N>>G;
    for(int i=1;i<=N;++i)
        fin>>V[i].W>>V[i].P;
}

int valid(int k)
{
    int S=0;
    if(X[k] <= X[k-1])
        return 0;
    for(int i=1;i<=k;++i)
        S+=V[X[i]].W;
    return S<=G;
}

void solutie(int k)
{
    int S2=0;
    for(int i=1;i<=k;++i)
        S2+=V[X[i]].P;
        if(S2>Max) Max=S2;
}

void Backtrack(int k)
{
    for(int i=1;i<=N;++i)
    {
        X[k]=i;
        if(valid(k))
           {
            solutie(k);
            if(k<N)
            Backtrack(k+1);
           }
    }
}

int main()
{
    Read();
    Backtrack(1);
    fout<<Max;
    return 0;
}