/*
TASK: lift
LANG: C++
*/
#include <stdio.h>
#include <time.h>
#include <set>
#include <algorithm>
using namespace std;
#define INF (int)1e9
#define MAXN (1<<15)

 int a[MAXN];
 int can[MAXN];
 int n,t;
 int x[16];
 int y[16];
 int res;

 struct cmp
  {
   bool operator() (const int p,const int q) const
    {
     if (a[p]!=a[q]) return a[p]<a[q];
     return p<q;
    }    
  };
 
 set<int,cmp> g;

 void init ()
  {
   int i,j,k,l;
   for (i=0;i<(1<<n)-1;i++)
    {
     a[i]=INF;
     g.insert(i);
    }
   a[i]=0;
   g.insert(i);
   memset(can,-1,sizeof(can));
   for (i=0;i<(1<<n);i++)
    {
     k=l=0;
     for (j=0;j<n;j++)
      if ((i>>j)&1)
       {
        k+=y[j];
        l=max(l,x[j]);
       }
     if (k<=t) can[i]=l;
    }
  }  

 int main ()
  {
   int i,j,k,pom;
   scanf("%d%d",&n,&t);
   for (i=0;i<n;i++)
    scanf("%d%d",&x[i],&y[i]);
   init();
   res=INF;
   while (!g.empty() && a[*g.begin()]!=INF)
    {
      i=*g.begin();
      g.erase(i);
      if (can[i]!=-1)
       res=min(res,can[i]+a[i]);
      if (a[i]>=res) continue;
      for (j=1;j<(1<<i);j++)
       if ((i&j)==j && can[j]!=-1)
        for (k=0;k<n;k++)
         if (!(((i^j)>>k)&1))
          {
           pom=(i^j^(1<<k));
           if (a[pom]>a[i]+can[j]+x[k])
            {
             g.erase(pom);
             a[pom]=a[i]+can[j]+x[k];
             g.insert(pom);
            }
          }
     }
   if (res==INF) res=0;
   printf("%d\n",res);
   return 0;
  }
  
