#include <iostream>
#include <fstream>
using namespace std;
/*
3. Implement a backtracking solution for the KSP and run it on DS8 and DS10 to obtain the respective
optimum solutions SB-8 and SB-10 (Backtracking should be useless on DS50 and DS100).
*/

int n,g,i,l;
int a[101],x,w; //for weight
int b[101],y,p; //for profit

void backtracking(int j)
{
    int i;
    for(i=j+1;i<=n;i++)
    {
        if(l>=a[i])
        {
            x+=a[i];
            l-=a[i];
            y+=b[i];
            if(y>p)
            {
                p=y;
                w=x;
            }
            else if(y==p && x<w)
            {
                w=x;
            }
            backtracking(i);
            x-=a[i];
            l+=a[i];
            y-=b[i];
        }
    }
}

int main()
{
    //ifstream fin("data.in");
    ifstream fin("rucsac.in");
    ofstream fout("rucsac.out");
    fin>>n>>g;
    for(i=1;i<=n;i++)fin>>a[i]>>b[i];
    for(i=1;i<=n;i++)
    {
        //cout<<a[i]<<" ";
        x=a[i];
        l=g-x;
        y=b[i];
        if(y>p)
        {
            p=y;
            w=x;
        }
        else if(y==p && x<w)
        {
            w=x;
        }
        backtracking(i);
    }
    //cout<<"Maximum profit: "<<p<<"\nWeight: "<<w;
    fout<<p;

    fin.close();
    fout.close();
    return 0;
}