#include<stdio.h>
#define INF 2000000000
struct MyStruct {int c,e;};
MyStruct a[1005];
int d[5005];
int min(int a,int b) {return a>b?a:b;}
int main()
{
	freopen("energii.in","r",stdin);
	freopen("energii.out","w",stdout);
	int n,g,i,j,smax=0;
	scanf("%d%d",&n,&g);
	for(i=1;i<=n;i++)
		scanf("%d%d",&a[i].e,&a[i].c);
	smax=0;d[0]=0;
	for(i=1;i<=g;i++)
		d[i]=INF;
	for(i=1;i<=n;i++)
	{
		for(j=smax;j>=0;j--)
			if(j+a[i].e<=g && d[j]!=INF && d[j+a[i].e]<d[j]+a[i].c)
				d[j+a[i].e]=d[j]+a[i].c;
		smax=min(smax+a[i].e,g);
	}
	int min=1000000000;
	for(i=1;i<=n;i++)
		for(j=g;j>=g-a[i].e;j--)
			if(d[j]+a[i].c<min)
				min=d[j]+a[i].c;
	for(i=1;i<=n;i++)
		if(a[i].c<min && a[i].e>g)
			min=a[i].c;
	printf("%d\n",min);
	return 0;
}