#include <stdio.h>
struct gen{
	int cant,cost;
}ge[1001];
FILE *f=fopen("energii.in","r"),*g=fopen("energii.out","w");
int gg,w;
unsigned long *a1,*a2;
unsigned long min(unsigned long a, unsigned long b){
	 if(a<b) return a;
	 return b;
}
void swap(unsigned long*&a1, unsigned long*&a2){
	unsigned long* z;
	z=a1;a1=a2;a2=z;
}
void swap(gen &a, gen&b){
	ge[0]=a;a=b;b=ge[0];
}
void citeste(){
	fscanf(f,"%d%d",&gg,&w);
	for(int i=1;i<=gg;i++) fscanf(f,"%ld%ld",&ge[i].cant,&ge[i].cost);
}
void ordonare(){
	int ok;
	do{
		ok=1;
		for(int i=1;i<gg;i++){
			if(ge[i].cost>ge[i+1].cost || (ge[i].cost==ge[i+1].cost && ge[i].cant>ge[i+1].cant)){swap(ge[i],ge[i+1]);ok=0;}
		}
	}while(!ok);
}
void init(){
	for(int i=1;i<=w;i++){ 
		if(i<=ge[1].cant) a1[i]=ge[1].cost;
		else a1[i]=500000;
	}
}
void dinamica(){int energie;
	init();
	for(int i=1;i<=gg;i++){
		for(int j=1;j<=w;j++){
			energie=j-ge[i].cant;
			if(energie<0){
				if(j==1) a2[j]=a1[j];
				else a2[j]=min(a1[j],ge[i].cost);
			}else{
				if(j==1) a2[j]=500000;
				else a2[j]=min(a1[j],ge[i].cost+a1[j]);
			}
		}swap(a1,a2);
	}
}
int main(){
	citeste();
	ordonare();
	a1=new unsigned long[5001];
	a2=new unsigned long[5001];
	init();
	dinamica();
	return 0;
}