/*
TASK: lift
LANG: C
*/
#include <stdio.h>
#include <time.h>
#define min(a,b) (((a)<(b))?(a):(b))
#define max(a,b) (((a)>(b))?(a):(b))
#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;

 void init ()
  {
   int i,j,k,l;
   for (i=0;i<(1<<n);i++) a[i]=INF;
   a[(1<<n)-1]=0;
   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;
   scanf("%d%d",&n,&t);
   for (i=0;i<n;i++)
    scanf("%d%d",&x[i],&y[i]);
   init();
   res=INF;
   for (i=(1<<n)-1;i>=0;i--)
    if (a[i]!=INF)
     {
      if (can[i]!=-1)
       res=min(res,can[i]+a[i]);
      for (j=1;j<(1<<i);j++)
       if ((i&j)==j && can[j]!=-1)
        for (k=0;k<n;k++)
         if ((!((i>>k)&1)) || ((j>>k)&1))
          a[i^j^(1<<k)]=min(a[i^j^(1<<k)],a[i]+can[j]+x[k]);
     }
   if (res==INF) res=0;
   printf("%d\n",res);
   return 0;
  }
  
