# include <stdio.h>

const int cost=0,energie=1,MAXGEN=1001,MAXW=5001;
const int INFINIT=-1;

int g,w;gen[MAXGEN][2];

void citire()
{
int i;
FILE *f=fopen("energii.in","r");
fscanf(f,"%d%d",&g,&w);
for (i=1;i<=g;i++)
	fscanf(f,"%d%d",&gen[i][energie],&gen[i][cost]);
fclose(f);
}

long int min(long int a, long int b)
{
if (a==INFINIT) return b;
if (a>b) return b;
return a;
}

int max(int a, int b) {if (a>b) return a; return b;}

long int calculeaza()
{
long int c[MAXW+3]={0};int j;
int i;
for (i=1;i<=w+1;i++) c[i]=INFINIT;
for (i=1;i<=g;i++)
	{
	//determina costul pentru cine a trecut deja de maxim
	for (j=w;j>=max(w-gen[i][energie]+1,0);j--)
		if (c[j]!=INFINIT)
			c[w+1]=min(c[w+1],c[j]+gen[i][cost]);
	//determin costul pentru restul
	for (j=w;j>=gen[i][energie];j--)
		if (c[j-gen[i][energie]]!=INFINIT)
			c[j]=min(c[j],c[j-gen[i][energie]]+gen[i][cost]);
	}
return min(c[w+1],c[w]);
}

void scrie(long int sol)
{
FILE *g=fopen("energii.out","w");
fprintf(g,"%ld\n",sol);
fcloseall();
}

int main()
{
citire();
scrie(calculeaza());
return 0;
}