#include <bits/stdc++.h>
using namespace std;
ifstream fin("energii.in");
ofstream fout("energii.out");

const int nmax = 5010;
const int inf = 1e9;

vector<int> dp(nmax,inf);
vector<pair<int,int>> values(nmax,{0,0});
int n,w;

void read_input(){
	fin >> n >> w;
	for(int i = 1; i <=n; i++){
		fin >> values[i].first >> values[i].second;
	}
}

void solve(){
	dp[0] = 0;
	
	for(int i = 1; i <=n; i++){
		for(int j = w; j >= 0; j--){
			if(dp[j] != inf){
				int weight = j + values[i].first;
				if(weight > w){weight = w;}
				dp[weight] = min(dp[weight],dp[j] + values[i].second);
			}		
		}
	};
	
	fout << dp[w];
}

int main(){
	read_input();
	solve();
	return 0;
}