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

#include <iostream>
#include <vector>
#include <time.h>
#include <algorithm>
#include <cstdlib>
using namespace std;
int N,T;
clock_t begin;
struct A{
	int i,j;
	int n;
	bool operator < (A t)
	const	{
			if(i<t.i) return 1;
			else if(i==t.i&&j<t.j) return 1;
			else return 0;
		}
		
	
	};
vector <A> v;	
long long tt=0;
long long tsum=99999999,sum=0;
bool s[16];
vector <int> t;
bool f[16];

void gen(int i,int br)
	{			
		if(br>N) return;		
		if(double(clock()-begin)/CLOCKS_PER_SEC>2.40) {
			if(tsum!=99999999)
				{
					cout<<tsum<<endl;
				}
				else cout<<"0"<<endl;
				exit(0);
			}
		int j;	
//	cout<<t.size()<<endl;		
		
	/*	for(j=0;j<N;j++)
						cout<<f[j]<<" ";
						cout<<endl;
		cout<<tt<<endl;
	*/
	
	
/*				for(j=0;j<N;j++)
						cout<<s[j]<<" ";
						cout<<endl;
	cout<<tt<<" "<<sum<<" "<<tsum<<endl;
*/				
		int q=0,q1=0;
		
/*		for(j=0;j<N;j++)
			{
				if(s[j]) {q1=1; break;}
			}
			if(q1==0&&i!=0) return;	
*/				
			for(j=0;j<N;j++)
				if(!s[j]) {q=1; break;}
			if(q==0&&tt<=T)
				{

			/*	for(j=0;j<N;j++)
						cout<<s[j]<<" ";
						cout<<endl;
			*/

				int maxi=-1;
				int k;
				for(k=0;k<t.size();k++)
					maxi=max(v[t[k]].i,maxi);
					//	cout<<maxi<<" "<<sum<<" "<<tsum<<endl;
					sum+=maxi;
							//				cout<<maxi<<" "<<sum<<" "<<tsum<<endl;
					if(tsum>sum)
						tsum=sum;
					sum-=maxi;	
				return;
				}	


		if(sum>=tsum) return;
		if(tt>=T)
			{
				int maxi=-1;
				int u=tt;
				s[t[t.size()-1]]=0;
				vector <int> h;
				tt=0;
				h=t;
				int k;
				for(k=0;k<t.size()-1;k++)
					maxi=max(v[t[k]].i,maxi);
					t.clear();
				sum+=maxi;
				for(k=0;k<N;k++)
					{
				if(s[k])
				{	
				s[k]=0;
				sum+=v[k].i;
				gen(0,br+1);
				sum-=v[k].i;
				s[k]=1;
				}
				}
				tt=u;

				t=h;	
				s[t[t.size()-1]]=1;
					sum-=maxi;
			}	
			if(i==N) return;
			if(tt>=T) return;
		
					if(!s[i])
						{
							s[i]=1;
							tt+=v[i].j;
							t.push_back(i);
							gen(i+1,br);
							s[i]=0;
							tt-=v[i].j;
							t.pop_back();
					}	
							gen(i+1,br);		

}
int main()
{
//	freopen("test.txt","r",stdin);
//	freopen("test1.txt","w",stdout);
	begin=clock();
	cin>>N>>T;
		int i;
			for(i=1;i<=N;i++)
				{
					A h;
					cin>>h.i>>h.j;
					v.push_back(h);
				}
			sort(v.begin(),v.end());
			for(i=0;i<v.size();i++)
				{
					v[i].n=i;
				//	cout<<v[i].i<<" "<<v[i].j<<" "<<v[i].n<<endl;
				}	
				gen(0,0);	
			if(tsum!=99999999)	
			cout<<tsum<<endl;
			else cout<<"0"<<endl;		
	return 0;
}
