#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,minim=INF,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;
			else
				if(j+a[i].e>g && d[j]!=INF && minim>d[j]+a[i].c)
					minim=d[j]+a[i].c;
		smax=min(smax+a[i].e,g);
	}
	printf("%d\n",minim);
	return 0;
}