#include <fstream>

using namespace std;
int N, G, v[5001], g[5001], x[100], vmax=0;
bool viz[5001];

ifstream fin("rucsac.in");
ofstream fout("rucsac.out");
void back(int k, int ga, int va)
{
    int i;
    for(i = 1;i <= N; i++)
    if(!viz[i] && ga + g[i] <= G)
        {
            viz[i]=1;
            if(ga + g[i] <= G && va + v[i] >vmax)
                vmax = va + v[i];
            if(ga + g[i] < G)
                back(k+1 , ga + g[i], va + v[i]);
            viz[i] = 0;
        }
}
int main()
{
    int i;
    fin>> N>> G;
    for( i = 1; i <= N; i++)
        fin>> g[i]>> v[i];
    back(1 , 0, 0);
    fout<< vmax<< "\n";
    return 0;
}