#include <stdio.h>
#define Nmax 1002
#define Wmax 5002
#define INF 1 << 30

int v[Nmax], E[Nmax], C[Nmax], n, W, i, j, pmax, sol;

int main () {
	
	FILE *f = fopen("energii.in", "r");
	FILE *g = fopen("energii.out", "w");
	
	fscanf(f, "%d %d", &n, &W);
	for (i = 1; i <= n; i++)
		fscanf(f, "%d %d", &E[i], &C[i]);
	
	for (i = 1, sol = INF; i <= n; i++)
		for (j = pmax; j >= 0; j--) {
			if (j + E[i] < W) {
				if (v[j] + C[i] < v[j + E[i]])
					v[j + E[i]] = v[j] + C[i];
				if (j + E[i] > pmax)
					pmax = j + E[i];
			}
			else if (v[j] + C[i] < sol)
				sol = v[j] + C[i];
		}
	
	if (sol != INF)
		fprintf(g, "%d", sol);
	else
		fprintf(g, "0");
	
	fclose(f); fclose(g);
	
	return 0;
}