/*
TASK:lift
LANG:C++
*/
#include <iostream>
using namespace std;
int limit,n,price;
struct P
{
       int t,w;
       bool there;
} per[20];
bool cmp(P A,P B)
{
     if(A.t==B.t) return A.w<B.w;
     return A.t<B.t;
}
bool can()
{
     for(int i=1;i<=n;i++)
             for(int j=1;j<=n;j++)
             {
                     if(i==j) continue;
                     if(per[i].w+per[j].w<=limit) return false;
             }
     return true;
}
bool done()
{
     for(int i=1;i<=n;i++)
             for(int j=1;j<=n;j++)
                     if((per[i].there&per[j].there)==0) return false;
     return true;
}
                     
void otivane();
void vru6tane();                  
int main()
{
    cin>>n>>limit;
    for(int i=1;i<=n;i++)
            cin>>per[i].t>>per[i].w;
    sort(per+1,per+n+1,cmp);
    if(can()) {cout<<0<<endl;return 0;}
    
    otivane();
    cout<<price<<endl;
     
}
void otivane()
{
     if(done()) return;
     int p=limit;
     int pr=0;
     for(int i=1;i<=n;i++)
     {
             if(!per[i].there && p-per[i].w>=0)
             {
                          pr=max(pr,per[i].t);
                          p-=per[i].w;
                          per[i].there=1;
             }
     }
      
      price+=pr;
      vru6tane();
}
void vru6tane()
{
     if(done()) return;
     bool dae=0;
     for(int i=1;i<=n;i++)
     if(per[i].there)
     {
               price+=per[i].t;
               per[i].there=0;
               otivane();
               dae=1;
               break;
     }
     
     if(!dae) {cout<<0<<endl;}
}
