#include <stdio.h>
#include <time.h>
#include <stdlib.h>
#include <limits.h>

#define FIN "energii.in"
#define FOUT "energii.out"

#define GEN 1002
#define ENERG 5002
#define MIN(a,b) ((a)<(b))?(a):(b)

int EG[GEN], CG[GEN], G, W;
int co[GEN][ENERG];

int cost(){
	int i,j;
	
	for(i=1; i <= W; i++){
		co[0][i] = INT_MAX;
	}
	
	for(i=1; i <= G; i++){
		for(j=1; j <= W; j++){
			//printf("EG[%d]=%d\n", i, EG[i]); 
			if(EG[i] > j){
				co[i][j] = MIN(co[i-1][j], CG[i]);
				//printf("co[%d][%d]=%d\n", i, j, co[i][j]);
			} else {
				//co[i][j] = MIN(co[i-1][j], co[i-1][j-EG[i]]);
				if(co[i-1][j] == INT_MAX && co[i-1][j-EG[i]] == INT_MAX){
					co[i][j] = INT_MAX;
				} else if (co[i-1][j] == INT_MAX){
					co[i][j] = co[i-1][j-EG[i]] + CG[i];
				} else if (co[i-1][j-EG[i]] == INT_MAX){
					co[i][j] = co[i-1][j];
				} else {
					co[i][j] = MIN(co[i-1][j], co[i-1][j-EG[i]]+CG[i]);
				}
			}
		}
	}
	/*
	printf("\n\n");
	for(i=0; i <= G; i++){
		for(j=0; j <= W; j++){
			if(co[i][j] == INT_MAX){
				printf("INF  ");
			} else {
				printf("%03d  ", co[i][j]);
			}
		}
		printf("\n\n");
	}
	*/
	return co[G][W];
}


int main(){
	clock_t start, end;
	float dur;
	int i;
	start = clock();
	
	FILE *in = fopen(FIN, "rt");
	FILE *out = fopen(FOUT, "wt");
	
	fscanf(in, "%d%d", &G, &W);
	for(i=1; i <= G; i++){
		fscanf(in, "%d%d", &EG[i], &CG[i]);
	}
	/*
	printf("GENERATOARE: %d\nENERGIE CERUTA: %d\n", G, W);
	for(i=1; i <= G; i++){
		printf("GENERATORUL %d produce %d energie pentru costul %d\n", i, EG[i], CG[i]);
	}
	*/
	fprintf(out, "%d", cost());
	
	end = clock();
	dur = (end - start) / (float) CLOCKS_PER_SEC;
	printf("Execution time: %gs", dur);	
	return 0;
}