/*
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 go(int);

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

bool isOn(int state,int ind) {
     return ( (state & (1<<ind) ) != 0 );
}

int rec(int w,int state,int firstState,int ch,int count,int last) {
    if(state == 0) return ch;
    int res = maxval;
    for(int i=last+1;i<n;i++) {
            if( w+v[i].w<=t && isOn(state,i) ) {
                int cur = rec(w+v[i].w, state-(1<<i), firstState, max(ch, v[i].h), count+1, i);
                if(res > cur) res = cur;
            }
    }
    if(count > 1) {
             FOR(i,n) {
                 if( isOn(firstState,i) && !isOn(state,i) ) {
                        int nst = state + (1<<i);
                        int cur = go(nst) + v[ i ].h + ch;
                        res = min(res, cur);
                 }
             }
    }
    return res;
}
int go(int state) {    
    if(dp[ state ] != -1) return dp[state];
    
    if(state == 0) return dp[state] = 0;
    
    
    int bits = 0;
    FOR(i,n) if(isOn(state,i)) bits++;
    
    int res = maxval;
    if(bits == 2) {
            int cbit[4];
            int cbitsz(0);
            FOR(i,n) if( isOn(state,i) ) {
                     cbit[cbitsz++] = i;
            }
            int cw = v[cbit[0]].w + v[cbit[1]].w;
            if(cw<=t) {
                     res = max( v[cbit[0]].h, v[cbit[1]].h );
            }
    }
    else {
        int cur = rec(0,state,state,0,0,-1);
        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;
    }
    int all(0);
    FOR(i,n) {
             all += v[i].w;
    }
    if(all <= t) {
           printf("%d\n",maxt);
           return 0;
    }
    
    memset(dp,-1,sizeof dp);
    
    int res;
    
    dp[0] = 0;
    res = go((1<<n) - 1);
    if(res>=maxval) {
                    printf("0\n");
                    return 0;
    }
    printf("%d\n",res);
        
    return 0;
}
