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

using namespace std;

struct tur
{
	int h,w;
};

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

int p[65536];
int pr(int c)
{
	if(p[c])
		return p[c];
	int res=0;
	for(int 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];;
}

int r[65536];
int ret(int c)
{
	if(r[c])
		return r[c];
	int res=30000,pos,w;
	for(int 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<<10)+pos;
	return r[c];
}

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

int cn[65536];
int cnt(int c)
{
	if(cn[c])
		return cn[c];
	int res=0;
	for(int i=0;i<16;i++)
		if(c&(1<<i))
			res++;
	cn[c]=res;
	return cn[c];
}

void rec(int h)
{
//	cout<<"rec("<<h<<")\n";
	if(h==0)
		if(res<mn)
		{
			mn=res;
			return;
		}
	int pqr=h;
	for(int yy=pqr&(-pqr);yy<=pqr;yy++)
	{
//		int 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)>>10);
						h=h^(1<<(ret(yy)&1023)-1);
//						cout<<"h="<<h<<"\n";
					}
					else
						res+=pr(yy);
//					cout<<res<<"\n";
					rec(h);
					if(h)
					{
						res-=pr(yy)+(ret(yy)>>10);
//						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()
{
	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;
}
