/*
TASK:lift
LANG:C++
*/
#include <stdio.h>
#include <string.h>
#include <algorithm>
#define min(a,b) (a < b ? a : b)
#define max(a,b) (a > b ? a : b)
#define FOR(i,n) for(int i=0;i<n;i++)
#define maxval 9999999
#define maxn 15

struct type {
       int h,w;
} v[ maxn ];

int dp[ (1<<maxn) ];
int n,t;
int maxt = -1;
int all[15],allSz(0);
bool used[15];
int gstate;
int go(int);

void printBits(int x) {
     while(x) {
              if((x&1)) printf("1");
              else printf("0");
              x>>=1;
     }
     printf("\n");
}

int rec(int w,int state,int ch,int count) {
    if(state == 0) return ch;
    int res = maxval;
    FOR(i,allSz) {
       if(!used[ all[i] ] && w+v[all[i]].w<=t) {
                 used[all[i]] = 1;
                 int cur = rec(w+v[all[i]].w,state - (1<<all[i]), max(ch, v[all[i]].h), count+1);
                 res = min(maxval, cur);
                 used[all[i]] = 0;         
       }
    }
    if(count > 1) {
             FOR(i,allSz) {
                if(used[ all[i] ]) {
                         int cur = go(state + (1<<i)) + v[ all[i] ].h + ch;
                         res = min(res, cur);
                }
             }
    }
    return res;
}

int go(int state) {
    if(dp[ state ] != -1) return dp[state] = 0;
    if(state == 0) return dp[state] = 0;
    allSz = 0;
    gstate=state;
    for(int i=n-1;i>=0;i--) {
             if( (state & (1<<i)) != 0) {
                 all[allSz] = i;
                 allSz++;
             }
             used[i] = 0;
    }
    
    int res = maxval;
    
    if(allSz == 2) {
             int cw = v[all[0]].w + v[all[1]].w;
             if(cw<t) {
                      res = max( v[all[0]].h, v[all[1]].h );
             }
    }
    else {
        int cur = rec(0,state,0,0);
        res = min(res, cur);
    }
    return dp[ state ] = res;
}

void init() {
     scanf("%d %d",&n,&t);
     FOR(i,n) {
              scanf("%d %d",&v[i].h, &v[i].w);
              if(maxt == -1) maxt = v[i].w;
              if(maxt < v[i].w) maxt = v[i].w;
     }
}

int main() {
    init();
    if(maxt > t) {
            printf("0\n");
            return 0;
    }
    memset(dp,-1,sizeof dp);
    dp[0] = 0;
    int res = go((1<<n) - 1);
    if(res>=maxval) {
                    printf("0\n");
                    return 0;
    }
    printf("%d\n",res);
    scanf("%d",&res);
    return 0;
}
