#include<fstream.h>
ifstream f("energii.in");
ofstream g("energii.out");
const int Nmax=1010;
const int Gmax=5010;
int n,E,a[Nmax][Gmax],en,cost;
int min(int x,int y)
{
 if(x<y)
	return x;
 return y;
}

void init()
{
 for(int i=0;i<=n;i++)
	for(int j=0;j<=E;j++)
		a[i][j]=32000;
}

void citire()
{
	f>>n;
	f>>E;
	init();
	for(long i=1;i<=n;i++)
	{
		f>>en>>cost;
		for(int j=1;j<=E;j++)
		{
			if(j<=en)
				a[i][j]=min(cost,a[i-1][j]);
			else
				a[i][j]=min(a[i-1][j],a[i-1][j-en]+cost);
		}
	}
}

int main()
{
 citire();
 g<<a[n][E];
 f.close();
 g.close();
 return 0;
}