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

struct gen
{
	int eg,cg;
} v[10010];

int g,w;
int 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 ()
{
	int i,j;
	freopen ("energii.in","r",stdin);
	freopen ("energii.out","w",stdout);
	scanf("%d",&g);
	scanf("%d",&w);
	for (i = 1;i <= g; ++i)
	{
		scanf("%d %d",&v[i].eg,&v[i].cg);
	}
	
	qsort(v,g,sizeof(gen),compar);
	
	for (i = 1;i <= g; ++i)
	{
		printf("%d %d\n",v[i].eg,v[i].cg);
	}
	
	for (i = 1;i <= w; ++i)
		sum[i] = 32765;
	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)
				sum[i + v[j].eg] = sum[i] + v[j].cg;
			
	printf ("%d",sum[w]);
	
	return 0;
}