#include<bits/stdc++.h>
#define N 5050
using namespace std;
int e[1020], g, dp[N], c[1020], i, w, j;
int main(){
	ifstream fin("energii.in");
	ofstream fout("energii.out");
	fin>>g>>w;
	for(i=1;i<=g;i++) fin>>e[i]>>c[i];
	for(i=0;i<=w;i++) dp[i]=999999;
	for(i=1;i<=g;i++)
		for(j=w; j>=1;j--){
            if (j > e[i]) {
            	if(dp[j-e[i]]+c[i]>dp[j]) dp[j]=dp[j-e[i]]+c[i];
			}
            else dp[j] = min(dp[j], c[i]);
        }
	fout<<dp[w];
	return 0;
}