#include <stdio.h>
#include <limits.h>
int n,w,v[5002],x,y,i,j;
int main() {
	FILE *f=fopen("energii.in","r");
	FILE *g=fopen("energii.out","w");
	fscanf(f,"%d%d",&n,&w);
	v[0]=0;
	for(i=1;i<=w;i++)
		v[i]=INT_MAX;
	for(i=1;i<=n;i++) {
		fscanf(f,"%d%d",&x,&y);
		for(j=0;j<=w;j++)
			if(v[j]!=INT_MAX)
				if(j+x<=w&&v[j]+y<v[j+x])
					v[j+x]=v[j]+y;
				else
					if(v[j]+y<v[w])
						v[w]=v[j]+y;
	}
	fprintf(g,"%d",v[w]);
	return 0;
}