/*
	Problema : energii.
	Categorie : PD- problema rucsacului.
	Autor : Ilinca Diana.
	Data : 28.04.2010
*/

#include <cstdio>

#define Nmax 1010
#define Wmax 5010
#define INF 1 << 30;

struct generator {int e, c;} G[Nmax];
int N, W;
int C[Nmax]; // C[i] = costul minim de a produce o cantitate de energie egala cu i

void citire () {
	
	int i;
	
	scanf ("%d", &N); // numarul de generatoare
	scanf ("%d", &W); // cantitatea de energie necesara repornirii centralei
	for (i = 1; i <= N; i++) 
		scanf ("%d %d", &G[i].e, &G[i].c); // energia produsa de un generator, respectiv costul sau
}

void dinamica () {

	int i, j, wmax = 0, w, c;
	
	for (i = 1; i <= W; i++)
		C[i] = INF; 
	
	C[0] = 0; // energie 0 => costul 0
	
	for (i = 1; i <= N; i++) { // parcurgem toate generatoarele si le integram in solutie
		// in vectorul C vom avea costul cu care putem produce cantitatea i de energie sau INF daca nu o putem atinge
		// wmax cantitatea maxima de energie produsa cu primele i-1 generatoare
		
		for (j = wmax; j >= 0; j--) {
			// folosim generatorul i. => daca adugam catitatea produsa de generatorul i la j ajungem in starea j + G[i].e
			w = j + G[i].e; 
			// costul va fi C[j] + G[i].c (costul actual de a ajunge in j + costul generatorului i)
			c = C[j] + G[i].c;
			
			if (w >= W) w = W; // are rost sa le luam pe alea mai mari ca W ? (logic ca nu).
			
			if (C[w] > c)
				C[w] = c; // actualizam costul daca se merita
			
			if (w > wmax) wmax = w;
		}
	}
	
	printf ("%d", C[w]);
	// De ce nu putem face for`ul de la 0 la wmax ? :d (pt acasa)
}

int main () {

	freopen ("energii.in", "r", stdin);
	freopen ("energii.out", "w", stdout);
	
	citire ();
	dinamica ();
	
	return 0;
}