#include <fstream>
#include <algorithm>

using namespace std;

ifstream f("energii.in");
ofstream g("energii.out");

int n,w,a[5001],i,j,d[5001][10001],b[5001];

int main(){
	f>>n>>w;
	for (i=1;i<=n;i++)
		f>>a[i]>>b[i];
	for(i=0; i<=n; i++)
	{
		d[i][0]=0;
	}
	for(i=0; i<=w; i++)
	{
		d[0][i]=99999999;
	}
	for (i=1;i<=n;i++){
		for (j=1;j<=w;j++){
			d[i][j]=d[i-1][j];
			if(j>a[i])
				d[i][j]=min(d[i][j], b[i]+d[i-1][j-a[i]]);
			else if(a[i]>=j)
				d[i][j]=min(d[i][j], b[i]);
		}
	}
	
	g<<d[n][w];
}