#include<stdio.h>
#define M 11000000
int p[100001];
int main(){
	int e[1001],c[1001],n,i,j,w;
	freopen("energii.in","r",stdin);
	freopen("energii.out","w",stdout);
	scanf("%d%d",&n,&w);
	for (i=0;i<n;++i){
		scanf("%d%d",&e[i],&c[i]);
	}
	for(i=1;i<=20000;++i)
		p[i]=M;
	p[0]=0;
	for(i=0;i<n;++i){
		for(j=w;j>0;--j)
			if(p[j]!=M){
				if(j+e[i]<w&&p[j+e[i]]>p[j]+c[i])
					p[j+e[i]]=p[j]+c[i];
				if(j+e[i]>=w&&p[w]>p[j]+c[i])
					p[w]=p[j]+c[i];
			}
		if(c[i]<p[e[i]])
			p[e[i]]=c[i];
	}
	printf("%d\n",p[w]);
	return 0;
}