#include <bits/stdc++.h>
using namespace std;

ifstream fin("energii.in");
ofstream fout("energii.out");

#define ll long long

const ll INF=LLONG_MAX/2;

int main(){
    int n,w;
    fin >>n >>w;
    ll ans=INF;
    vector<int> eg(n+1, 0), ec(n+1,0);
    for(int i=1;i<=n;++i){
        fin>>eg[i]>>ec[i];
        if(eg[i]>=5000){
            ans=min((ll)ec[i], ans);
            --i;
            --n;
        }
    }
    vector<vector<ll>> dp(n+1, vector<ll>(5003, INF));
    for(int i=1;i<=n;++i){
        dp[i][eg[i]]=ec[i];
        for(int e=eg[i];e<=5000;++e){
            dp[i][e]=min({
                dp[i][e],
                dp[i-1][e],
                dp[i-1][e-eg[i]]+ec[i]
            });
        }
    }
    for(int i=w;i<=5000;++i)
        ans=min(ans,dp[n][i]);
    fout<<ans;
}