#include<fstream>
#include<iostream>
using namespace std;
int n,g;
int gr[5001],p[5001];
int a[2][100001];
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++ ){
		
		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];
				}
			}
		}
		l=1-l;
	}
	gi<<a[l][g]<<"\n";
	return 0;
}