#include <cstdio>

int a[2][5002];

void make_empty(bool currentline,int max) {
	for (int i=0;i<=max;i++) {
		a[currentline][i] = 0;
	}
}

int main() {
	FILE *ff,*gg;
	ff = fopen("energii.in","r");
	gg = fopen("energii.out","w");
	int g, w;
	fscanf(ff,"%d\n%d\n",&g,&w);
	int e,c;
	bool currentline=1;
	fscanf(ff,"%d %d\n", &e, &c);
	a[0][e] = c;
	for (int i=1; i<g; ++i) {
		fscanf(ff,"%d %d\n", &e, &c);
		//berakja az elotte levo elemeket
		for (int j=1; j<e; j++) {
			a[currentline][j] = a[!currentline][j];
		}
		if (a[!currentline][e]<c) a[currentline][e]=c; else a[currentline][e] = a[!currentline][e];
		//az elemtol kezdodoen
		for (int j=e+1; j<=w; j++){
			if (a[!currentline][j]==0) continue;
			if (a[!currentline][j]>a[!currentline][j-e]+c) a[currentline][j]=c;
		}
		currentline = !currentline;
		make_empty(currentline,w+1);
	}
	fprintf(gg,"%d",a[!currentline][w]);
	fclose(ff);
	fclose(gg);
	return 0;
}