/*
TASK:lift
LANG:C++
*/
#include<stdio.h>
#define MAX 16384
#define max(a,b) (a>b?a:b)
int n,t,x,p2[20],height[20],weight[20];
int masiv1[17000],masiv2[17000];
bool used1[17000],used2[17000];

void rec1(int start);
void rec2(int start);


int main()
{
scanf("%d%d",&n,&t);
for(x=0;x<n;x++)
                scanf("%d%d",&height[x],&weight[x]);
p2[0]=1;
for(x=1;x<20;x++)
                 p2[x]=p2[x-1]*2;
x=0;
masiv2[0]=0;
used1[0]=1;
used2[0]=1;
rec1(p2[n]-1);

printf("%d\n",masiv1[p2[n]-1]);
return 0;
}


void rec1(int start)
{
masiv1[start]=MAX;
int w,sum,x,y;
used1[start]=1;

for(x=1;x<=start;x++)
if((start-x)==(start^x))
{
w=0;
sum=0;
for(y=0;y<n;y++)
                if(p2[y]&x)
                           {
                           w+=weight[y];
                           sum=max(sum,height[y]);
                           }
if(w<=t)
        {
        /* ekvivalentno na start-x */
        if(!used2[start^x])
                          rec2(start^x);
        if(masiv2[start^x]+sum<masiv1[start])
                                      masiv1[start]=masiv2[start^x]+sum;
        }
}


return;
}


void rec2(int start)
{
masiv2[start]=MAX;

int w,sum,x,y;
used2[start]=1;

for(x=1;x<=p2[n]-1-start;x++)
/*for(y=1;y<=x;y<<1)                  if(y&x)       if(!(y&start))                                       break;*/
if((start+x)==(start^x))
{
w=0;
sum=0;
          for(y=0;y<n;y++)
                          if(p2[y]&x)
                                     {
                                     w+=weight[y];
                                     sum=max(sum,height[y]);
                                     }
if(w<=t)
        {
        /* ekvivalentno na start-x */
        if(!used1[start^x])
                           rec1(start^x);
        if(masiv1[start^x]+sum<masiv2[start])
                                      masiv2[start]=masiv1[start^x]+sum;
        }
}

return;
}
