/*
LANG:C++
TASK:lift
*/
#include <stdio.h>
#include <string.h>
#include <algorithm>
#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);

int go(int);

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

int rec2(int state) {
    int res = -1;
    do {
        for(int j=2;j<allSz;j++) {
            bool possible(true);
            int cw(0);
            int nst = state;
            int maxh = 0;
            for(int k=0;k<j;k++) {
                    cw += v[ all[k] ].w;
                    if(cw>t) {
                             possible = false;
                             break;
                    }
                    nst -= (1 << (all[k]));
                    if(maxh < v[ all[k] ].h) maxh = v[ all[k] ].h;
            }
            if(possible) {
                         for(int k=0;k<j;k++) {
                             int cur = go(nst + (1<<all[k]));
                             cur += maxh + v[all[k]].h;
                             if(res==-1) res = cur;
                             else if(res>cur) res = cur;
                         }
            }
            else break;
        }
    } while(std::next_permutation(all,all+allSz));
    
    return res;
}

int go(int state) {
    if(dp[ state ] != -1) return dp[state] = 0;
    if(state == 0) return dp[state] = 0;
    allSz = 0;
    for(int i=n-1;i>=0;i--) {
             if( (state & (1<<i)) != 0) {
                 all[allSz] = i;
                 allSz++;
             }
    }
    int res = -1;
    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 {
        res = rec2(state);
    }
    if(res==-1) res = maxval;
    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;
}
