/*
TASK: lift
LANG: C++
*/
#include <iostream>
#include <fstream>
#include <vector>
#include <string>
using namespace std;

#define MAXN 15
#define MAXT 500
int n,t;

bool used[65536];
int step[16]={1,2,4,8,16,32,64,128,256,512,1024,2048,4096,8192,16384,32768};

struct Q {
   bool p[15];      
   bool lift;
   int money;
};

struct P {
   int t;
   int h;       
};

P people[MAXN];

int coding(Q q) {
    int ret=0;
    int i;
    for(i=0;i<n;i++) {
        if(q.p[i]) {
            ret += (1<<i);       
        }                 
    }
    if(q.lift)ret += (1<<15);
    return ret;
}

int main() {
    int i,j;
    int ret=0;
    cin>>n>>t;
    for(i=0;i<n;i++) {
       cin>>people[i].h>>people[i].t;                 
    }
    vector<Q> queue(7000000);
    //cout<<sizeof(queue)<<endl;
    Q start;
    start.money=0;
    start.lift=0;
    for(i=0;i<n;i++)start.p[i]=0;
    Q curr,tmp;
    used[coding(start)]=1;
    queue[0]=start;
    int qstart=0,qend=1;
    while(qstart<qend) {
        //cout<<'h'<<endl;
        curr = queue[qstart++];
        int cod = coding(curr);
        int comp=(1<<15);
        comp += step[n]-1;
        //cout<<cod<<" "<<comp<<endl;
        //cout<<curr.lift<<" "<<curr.money<<endl;
        //
        //cout<<curr.lift<<" ";
        //for(j=0;j<n;j++) cout<<curr.p[j]<<" ";
        //cout<<curr.money<<" ";
        //cout<<endl;
        //
        if(cod==comp) {
            //cout<<'h'<<endl;
            if(ret==0 || curr.money < ret)ret=curr.money;
            //continue;      
        }              
        //tmp.money=curr.money;
        //tmp.lift=curr.lift;     
        for(i=1;i<step[n];i++) {
            for(j=0;j<n;j++)tmp.p[j]=curr.p[j];
            tmp.money=curr.money;
            if(curr.lift==1)tmp.lift=0;
            else tmp.lift=1;
            //tmp.lift=!curr.lift;
            int highest=0;
            int sum=0;
            for(j=0;j<n;j++) {
               if(curr.p[j]==curr.lift && (i&(1<<j))) {
                    if(highest<people[j].h)highest=people[j].h;
                    sum += people[j].t;
                    if(curr.p[j]==1)tmp.p[j]=0;
                    else tmp.p[j]=1;
                    //tmp.p[j]=!curr.p[j];                    
               }                 
            }
            //cout<<highest<<" "<<sum<<" "<<tmp.lift<<endl;
            //for(j=0;j<n;j++)cout<<tmp.p[j]<<" ";
            //cout<<endl<<endl;
            //int ttt;
            //cin>>ttt;
            if(sum<=t && sum>0) {
                tmp.money+=highest;
                //if(!used[coding(tmp)]) {
                  //  used[coding(tmp)]=1;
                    queue[qend++]=tmp;
                    if(qend>=7000000){qstart=qend;break;}                   
                //}           
            }         
        }
    }
    cout<<ret<<endl;
    //cin>>i;
    return 0;   
}
