#include<stdio.h>
#define N 1005

void read(),solve(int k),sort(),hd(int ii, int nn), sw(int i1, int i2);

int G,n,i,w[N],cost[N],Cmin=32000,sol;

int main()
{	
	read();
	sort();
	solve(0);
	printf("%d\n",Cmin);
	return 0;
}

void read()
{	
	freopen("energii.in","r",stdin);
	freopen("energii.out","w",stdout);
	
	scanf("%d%d",&n,&G);
	for(i=1;i<=n;i++) scanf("%d%d",&w[i],&cost[i]);
}

void sort()
{	
	for(i=n/2;i>=1;i--) hd(i,n);
	for(i=n;i>=1;i--){ sw(1,i); hd(1,i-1);}
}

void hd(int ii, int nn)
{	
	int is=ii*2;
	if(is>nn) return;
	if(is<nn) if(cost[is]<cost[is+1]) is++;
	if(cost[ii]<cost[is]){ sw(ii,is); hd(is,nn);}
}

void sw(int i1, int i2)
{	
	int
	aux=w[i1]; w[i1]=w[i2]; w[i2]=aux;
	aux=cost[i1]; cost[i1]=cost[i2]; cost[i2]=aux;
}
	
void solve(int k)
{	
	if(sol>=Cmin) return;
	if(G<=0){ Cmin=sol; return;}
	if(k==n)  return;

	solve(k+1);		  

	sol+=cost[k+1]; G-=w[k+1];
	solve(k+1);
	sol-=cost[k+1]; G+=w[k+1];
}