
/*
TASK:lift
LANG:C
*/

//#define DEBUG

#include<stdio.h>
#include<time.h>

void rec(int ,int ,int ,int ,int );

int m1=-1,m1i,m2=-1,m2i;
int m;
int n,t;
int theside[16]={0};
int theotherside[16]={0};
int a[16][2];

int main () {
    int i;
    #ifdef DEBUG
    freopen("test.txt","rt",stdin);
    #endif
    clock();
    scanf("%d %d",&n,&t);
    for (i=0;i<n;i++) {
        scanf("%d %d",&a[i][0],&a[i][1]);
        if (a[i][1]>t) {
           printf("0\n");
           return 0;
           }
        theside[i]=1;
        }
    for (i=0;i<n;i++)
        if (a[i][1]<m1||m1==-1) {
           m1=a[i][1];
           m1i=i;
           }
        else if (a[i][1]==m1)
             if (a[i][0]<a[m1i][0])
                m1i=i;

    for (i=0;i<n;i++)
        if (m1+a[i][1]<=t)
           break;
    if (i==n) {
       printf("0\n");
       return 0;
       }

    for (i=0;i<n;i++)
        if (i!=m1i)
        if (a[i][1]<m2||m2==-1) {
           m2=a[i][1];
           m2i=i;
           }
        else if (a[i][1]==m2)
             if (a[i][0]<a[m2i][0])
                m2i=i;


              
    m=(a[m1i][0]+(a[m2i][0]<<1))*(n-2);
    for (i=0;i<n;i++)
        if (i!=m1i&&i!=m2i)
           m+=a[i][0];
           
    rec(-1,0,0,0,0);
    
    printf("%d\n",m);
    return 0;
    }

void rec(int lastused,int totalmass,int maxheight,int mannum,int sum) {
     int i;
     if (sum+maxheight>m) return ;
     if  (((double)clock()/CLOCKS_PER_SEC)>2.46) {
         printf("%d\n",m);
         exit(0);
         }
     for (i=lastused+1;i<n;i++)
         if (theside[i]&&totalmass+a[i][1]<t) {
            theside[i]=0;
            theotherside[i]=1;
            rec(i,totalmass+a[i][1],((maxheight>a[i][0])?(maxheight):(a[i][0])),mannum+1,sum);
            theotherside[i]=0;
            theside[i]=1;
            }
     if (mannum<2) {
        for (i=0;i<n;i++)
            if (theotherside[i])
               break;
        for (i++;i<n;i++)
            if (theotherside[i])
               break;
        if (i>=n)
           return ;
        }
     for (i=0;i<n;i++)
         if (!theotherside[i]) break;
     if (i==n) {
        if (m>sum+maxheight)
           m=sum+maxheight;
        return ;
        }
     for (i=0;i<n;i++)
         if (theotherside[i]) {
            theotherside[i]=0;
            theside[i]=1;
            rec(-1,0,0,0,sum+maxheight+a[i][0]);
            theside[i]=0;
            theotherside[i]=1;
            }
     return ;
     }
