#include <iostream>
#include <fstream>
#define nr 5000+1

using namespace std;
ifstream in("rucsac.in");
ofstream out("rucsac.out");
pair<int,int> v[nr];
int N,G,count;
bool sol[nr];
bool is_sol(int k)
{
    if(k<N)
        return false;
    int g=0;
    for(int i=1;i<=N;++i)
        if(sol[i])
            g+=v[i].first;
    return g<=G;
}
int sum()
{
    int s=0;
    for(int i=1;i<=N;++i)
        if(sol[i])
            s+=v[i].second;
    return s;
}
void back(int k)
{
    for(short i=0;i<=1;++i)
    {
        sol[k]=i;
        if(is_sol(k))
            count=max(count,sum());
        else if(k<N)
            back(1+k);
    }
}
int main()
{
    in>>N>>G;
    for(int i=1;i<=N;++i)
        in>>v[i].first>>v[i].second;
    back(1);
    out<<count;
    return 0;
}