#include <fstream>

using namespace std;

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

int n,greutate,v[5005],prof[5005],gr[5005],G,pmax;

int valid(int k)
{

    greutate=0;
      for(int i=1 ;i<=k;i++)
      {

      if(v[i]) greutate+=gr[i];
      if(greutate>G)
      return 0;
      }
      return 1;
}

void afis(int k)
{
    int pret=0;
            for(int i=1;i<=k;i++)
            {
             if(v[i]) pret+= prof[i];
             if(pret>pmax)pmax=pret;
            }


}
int sol(int k)
{
    if(k==n) return 1;
    return 0;
}
void bk(int k)
{
     for(int i=0;i<=1;i++)
        {
           v[k]=i;
           if(valid(k))
           {
           if (k==n) afis(k);
           else bk(k+1);
        }
    }
}


int main()
{
    f>>n>>G;
    for(int i=1;i<=n;i++)
    {
        f>>gr[i]>>prof[i];
    }

    bk(1);
    g<<pmax<<'\n';
    return 0;
}