/*
TASK:lift
LANG:C++
*/
#include <iostream>

using namespace std;

struct tur
{
	unsigned short h,w;
};

unsigned short n,h,m1=0,m2=0,t,i,cw,c,mn=30000;
int res;
tur a[16];

unsigned short p[65536];
inline unsigned short pr(unsigned short c)
{
	if(p[c])
		return p[c];
	unsigned short res=0;
	for(unsigned short i=0;i<n;i++)
		if(c&(1<<i))
			if(a[i+1].h>res)
				res=a[i+1].h;
	p[c]=res;
	return p[c];
}

unsigned short r[65536];
int ret(unsigned short c)
{
	if(r[c])
		return r[c];
	int res=30000,pos,w;
	for(unsigned short i=0;i<n;i++)
		if(c&(1<<i))
		{
			if(a[i+1].h<res)
			{
				pos=i+1;
				res=a[pos].h;
				w=a[pos].w;
			}
			if(a[i+1].h==res)
				if(a[i+1].w<w)
				{
					pos=i+1;
					res=a[pos].h;
					w=a[pos].w;
				}
		}
	r[c]=(res<<4)+pos;
	return r[c];
}

unsigned short w[65536];
inline unsigned short wght(unsigned short c)
{
	if(w[c])
		return w[c];
	unsigned short res=0;
	for(unsigned short i=0;i<n;i++)
		if(c&(1<<i))
			res+=a[i+1].w;
	w[c]=res;
	return w[c];
}

unsigned short cn[65536];
inline unsigned short cnt(unsigned short c)
{
	if(cn[c])
		return cn[c];
	unsigned short res=0;
	for(unsigned short i=0 ;i<n;i++)
		if(c&(1<<i))
			res++;
	cn[c]=res;
	return cn[c];
}

void rec(unsigned short h)
{
//	cout<<"rec("<<h<<")\n";
	if(h==0)
		if(res<mn)
		{
			mn=res;
			return;
		}
	unsigned short pqr=h;
	for(unsigned short yy=pqr&(-pqr);yy<=pqr;yy++)
	{
//		unsigned short i=yy;
//		cout<<i<<" "<<cnt(i)<<" "<<pr(i)<<" "<<(ret(i)>>10)<<" "<<(ret(i)&1023)<<" "<<wght(i)<<"\n";
//		system("pause");
		if((yy&pqr)==yy)
			if((cnt(yy)>1)||(yy==t))
				if(wght(yy)<=t)
				{
					h=pqr^yy;
//					cout<<"pqr="<<pqr<<"\n";
					if(h)
					{
						res+=pr(yy)+(ret(yy)>>4);
						h=h^(1<<(ret(yy)&15)-1);
//						cout<<"h="<<h<<"\n";
					}
					else
						res+=pr(yy);
//					cout<<res<<"\n";
					rec(h);
					if(h)
					{
						res-=pr(yy)+(ret(yy)>>4);
//						h=h^(ret(yy)&1023);
//						cout<<"h="<<h<<"\n";
					}
					else
						res-=pr(yy);
//					h=h^yy;
//					cout<<"yy="<<yy<<"h="<<h<<"\n";
//					cout<<res<<"\n";
				}
	}
}

int main()
{
//	cout<<sizeof(unsigned short)<<"\n";
	cin>>n>>t;
	h=(1<<n)-1;
//	cout<<h<<"\n";
	for(i=1;i<=n;i++)
	{
		cin>>a[i].h>>a[i].w;
		if(a[i].w>m1)
		{
			m1=a[i].w;
			continue;
		}
		if(a[i].w>m2)
			m2=a[i].w;
	}
	if(m1+m2>t)
	{
		cout<<"0\n";
		return 0;
	}
//	cout<<"...\n";
//	for(i=1;i<=h;i++)
//		cout<<i<<" "<<pr(i)<<" "<<(ret(i)>>10)<<" "<<(ret(i)&1023)<<" "<<wght(i)<<"\n";
	rec(h);
	cout<<mn<<"\n";
    return 0;
}
