#include <cstdio>

const int W = 5001, INF = 2000000000;

int w;
int cst[W]; //a[energ] = costul minim pentru a produce energ energie.

void adaugare(int energ,int cost)
{
	int copie_energ;
	for (int i = w-1; i >= 0; --i)
	{
		if (cst[i] == INF)//Configuratia nu exista.
			continue;
		copie_energ=energ;
		if (i+energ > w)
			energ = w-i;//Montez toate rezultatele care produc mai mult de w energie tot in cst[w].
		if (cst[i] + cost < cst[i+energ])
			cst[i+energ] = cst[i]+cost;
		energ=copie_energ;//Refac energ-ul daca l-am modificat pentru urmatoarele configuratii.
	}
}

void initializare()
{
	cst[0]=0;
	for (int i = 1; i <= w; ++i)
		cst[i] = INF;
}

void citire()
{
	int energ,cost,g;
	scanf("%d%d",&g,&w);
	initializare();
	for (int i = 1; i <= g; ++i)
	{
		scanf("%d%d",&energ,&cost);
		adaugare(energ,cost);
	}
}

int main()
{
	freopen("energii.in","r",stdin);
	freopen("energii.out","w",stdout);
	citire();
	printf("%d",cst[w]);
	return 0;
}