#include<fstream>
#include<iostream>
using namespace std;
int n,g;
int gr[5010], p[5010];
int a[2][10010];
int i,cg;
int main()
{
	ifstream f("rucsac.in");
	ofstream gi("rucsac.out");
	f>>n>>g;
	for(i=1;i<=n;i++){
		f>>gr[i]>>p[i];
	}
 	int l=0;
	for(i = 1; i <= n; i++ ){
		l=1-l;
		for(cg = 0; cg <= g; cg++)
		{
			a[1-l][cg]=a[l][cg];
			if(gr[i]<=cg)
				if(a[1-l][cg]>a[l][cg-gr[i]]+p[i])
					a[1-l][cg]=a[1-l][cg];
				else
					a[1-l][cg]=a[l][cg-gr[i]]+p[i];
		}
	}
	gi<<a[l][g]<<"\n";
	return 0;
}