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

#include<iostream>
#include<vector>
#define pb push_back
//#include<conio.h>
using namespace std;
int i,j,n,T,m,tg;
struct qq{
	int h,t;
}b[20];
int viso4;
vector<int>a;

bool cmp(qq q,qq w){
	if(q.h>w.h)return 1;
    if(q.h==q.h && q.t<w.t)return 1;
    else return 0;
}
void init(){

//	freopen("inp3.txt","rt",stdin);
//    freopen("ssss.txt","wt",stdout);
    cin>>n>>T;
    for(i=1;i<=n;i++)cin>>b[i].h>>b[i].t;
//    n=10;
    for(i=1;i<=n;i++)a.pb(i);
    sort(b+1,b+n+1,cmp);
//    for(i=1;i<=n;i++)cout<<b[i].h<<endl;
}

int find_result(){
	int curh,curt,ans=0;
    //cout<<"asdasfsd"<<tg<<endl;
//    for(i=0;i<a.size();i++)cout<<a[i]<<" ";
//    cout<<endl;
    while(a.size()>0){
    	curh=viso4;
        curt=0;
    //    cout<<"\ngrupa:\n";
    	for(i=0;i<a.size();){
    		//cout<<a[i]<<" ";
            if(curt+b[a[i]].t<=tg){
            	curh=max(curh,b[a[i]].h);
                curt+=b[a[i]].t;
    //            cout<<a[i]<<" ";
        //        cout<<"->"<<a.size()<<" i="<<i<<endl;
                a.erase(a.begin()+i);
            }
            else i++;
    	}
        if(curt==0){
        	return -1;
        }
        else {
        	ans+=curh;//current group
            ans+=viso4;//back
        }
    //    cout<<"ans do tuk e "<<ans<<endl;
    }
    ans-=viso4;
//    cout<<endl;
    return ans;
}
int best=9999999;
void choose(){
	int asd,ans;
	for(asd=1;asd<=n;asd++){
    	a.erase(a.begin()+asd-1);
        tg=T-b[asd].t;
        viso4=b[asd].h;
    //    cout<<"lodkar:"<<asd<<endl;
        int ans=find_result();
    //    cout<<"ans za lodkar "<<asd<<" e "<<ans<<endl;
        if(ans!=-1)best=min(best,ans);
        for(i=1;i<=n;i++)a.pb(i);
    }
    if(best==9999999)cout<<"0\n";
    else cout<<best<<endl;
}

void solve(){
	choose();
}

int main(){  //clrscr();
	init();
    solve();
    return 0;
}

