#include <stdio.h>
#include <stdlib.h>

struct gen
{
	long eg,cg;
} v[1010];

long g,w;
long sum[5010];
int compar(const void *a,const void *b)
{
	gen c = *(gen *)a;
	gen d = *(gen *)b;
	if (c.eg != d.eg)
		return c.eg - d.eg;
	return c.cg - d.cg;
	
}



int main ()
{
	long i,j;
	freopen ("energii.in","r",stdin);
	freopen ("energii.out","w",stdout);
	scanf("%ld",&g);
	scanf("%ld",&w);
	for (i = 1;i <= g; ++i)
	{
		scanf("%ld %ld",&v[i].eg,&v[i].cg);
	}
	
	qsort(v,g,sizeof(gen),compar);

	for (i = 1;i <= w; ++i)
		sum[i] = 2000000000;
	sum[0] = 0;
	for (i = 0;i <= w; ++i)
		for (j = 1;j <= g; ++j)
			if (sum[i + v[j].eg] > sum[i] + v[j].cg && i+v[j].eg <= w)
				sum[i + v[j].eg] = sum[i] + v[j].cg;
	
	
	printf ("%ld",sum[w]);
	
	return 0;
}