/*
TASK:lift
LANG:C++
*/

#include <cstdio>
//#include <conio.h>
#include <algorithm>
#include <queue>
using namespace std;

#define MS      (1<<15)
#define INF     100000000

struct pers {
    int h,w;
};

pers P[16];
int N,T;

int gr_b[MS];
int gr_h[MS];
int grn=0;

int d[MS][2];
queue<int> Q,Q1;


int main()
{
    //freopen("a3.in","r",stdin);
    
    scanf("%d%d",&N,&T);
    for (int i=0;i<N;++i) scanf("%d%d",&P[i].h, &P[i].w);
    
    // prep.
    for (int b=1;b<(1<<N);++b) {
        int w=0;
        int h=0;
        for (int i=0;i<N;++i) {
            if (b & (1<<i)) {
                w+=P[i].w;
                h=max(h,P[i].h);
            }
        }
        if (w<=T) {
            gr_b[grn]=b;
            gr_h[grn]=h;
            ++grn;
        }
    }
    //printf("%d \n",grn);
    
    for (int i=0;i<MS;++i) d[i][0]=d[i][1]=INF;
    d[(1<<N)-1][0]=0;
    
    Q.push( (1<<N)-1 );
    
    int st,nst;
    int ans=0;
    
    for (int br=0; !Q.empty(); br=!br) {
        //printf("iter br=%d\n",br);
        for (;!Q.empty();) {
            st=Q.front(); Q.pop();
            //printf("%d\n",st);
            
            if (st==0) {
                //printf("ok %d (st=%d br=%d)\n",d[st][br], st,br);
                //getch();
                ans=d[st][br];
                goto prog_end;
            }
            
            if (br==0) {
                for (int i=0;i<grn;++i) {
                    if ((st & gr_b[i])==gr_b[i]) {
                        nst=st-gr_b[i];
                        if (d[nst][1] > d[st][0]+gr_h[i]) {
                            d[nst][1] = d[st][0]+gr_h[i];
                            Q1.push( nst );
                        }
                    }
                }
            }
            
            if (br==1) {
                for (int i=0;i<grn;++i) {
                    if ((st & gr_b[i])==0) {
                        nst=st+gr_b[i];
                        //printf("%d\n",nst);
                        if (d[nst][0] > d[st][1]+gr_h[i]) {
                            d[nst][0] = d[st][1]+gr_h[i];
                            Q1.push( nst );
                        }
                    }
                }
            }
        }
        swap(Q,Q1);
    }
    
    prog_end:;
    
    printf("%d\n",ans);
    
    
    //getch();
    return 0;
}
