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

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

long g,w;
long sum[5010],sel[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);

	scanf("%ld",&g);
	scanf("%ld",&w);
	for (i = 1;i <= g; ++i)
	{
		scanf("%ld %ld",&v[i].eg,&v[i].cg);
	}
	
	qsort(v,g+1,sizeof(gen),compar);
/*
	for (i = 1;i <= g; ++i)
	{
		printf("%ld %ld\n",v[i].eg,v[i].cg);
	}
*/	
	for (i = 1;i <= 5009; ++i)
		sum[i] = 2000000000;
	sum[0] = 0;
	sel[0] = 1;
	for (i = 1;i <= g; ++i)
		for (j = w;j >= 0; --j)
			if (j+v[i].eg <= w) // ultima e conditie de optimizare
				if (sel[j] && sum[j + v[i].eg] > sum[j] + v[i].cg)
				{
					sum[j + v[i].eg] = sum[j] + v[i].cg;
					sel[j + v[i].eg] = 1;
				}
	
	freopen ("energii.out","w",stdout);
	printf ("%ld\n",sum[w]);
	return 0;
}