#include<fstream>
using namespace std;
int i,j,n,g[5005],c[10010],a[10005],b[10005],greut;
int main(){
	ifstream f("rucsac.in");
	ofstream gi("rucsac.out");
	f>>n>>greut;
	for (i=1;i<=n;i++)
		f>>g[i]>>c[i];
	for (i=1;i<=n;i++){
		for (j=1;j<=greut;j++)
			if (j>=g[i]){
				if (a[j]>a[j-g[i]]+c[i])
					b[j]=a[j];
				else 
					b[j]=a[j-g[i]]+c[i];
			}
			else
				b[j]=a[j];
			for (j=1;j<=greut;j++)
				a[j]=b[j];
	}
	gi<<a[greut];
	return 0;
}