#include <fstream>

std::ifstream f("energii.in");
std::ofstream g("energii.out");

const int NMAX = 5005;
const int INF = (1LL << 31) - 1;

int G,W,dp[NMAX];
std::pair<int,int>v[NMAX];

int main(){
    
    f >> G >> W;
    
    for(int i = 1;i <= G;++i)
        f >> v[i].first >> v[i].second;
    
    for(int i = 0;i <= W;++i)
        dp[i] = INF;
    
    for(int i = 1;i <= G;++i){
        
        for(int j = NMAX;j - v[i].first >= 0;--j)
            if(dp[j - v[i].first] != INF)
                dp[j] = std::min(dp[j],dp[j - v[i].first] + v[i].second);
        
        dp[v[i].first] = std::min(dp[v[i].first],v[i].second);
    }
    
    g << dp[W];
    
    return 0;
}