#include<fstream>
#include<iostream>
using namespace std;
int n,g;
int gr[5010], p[5010];
int a[2][10010];
int i,cg;
int main()
{
	freopen("rucsac.in", "r", stdin);
	ofstream gi("rucsac.out");
	scanf ("%d %d", &n, &g);
	for(i=1;i<=n;++i){
		scanf ("%d %d", &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;
}