#include <fstream>
#include <vector>
#define int long long
using namespace std;
ifstream cin("energii.in");
ofstream cout("energii.out");
const int Vmax = 10001;
int n, G, step, ans = Vmax;
struct ob
{
    int Ep, Ec;
};
vector <ob> v;
vector <vector<int>> dp;
int32_t main()
{
    cin >> n >> G;
    v.resize(n+1);
    for(int i=1; i<=n; i++)
        cin >> v[i].Ep >> v[i].Ec;

    dp.assign(2, vector<int>(Vmax, 0));
    for(int i=1; i<=n; i++, step = 1 - step)
    {
        dp[step].assign(Vmax, 0);
        for(int j=0; j<=Vmax; j++)
        {
            dp[step][j] = dp[1-step][j];
            if(j >= v[i].Ep && dp[1-step][j-v[i].Ep] + v[i].Ec > dp[step][j])
                dp[step][j] = dp[1-step][j-v[i].Ep] + v[i].Ec;
        }
    }
    step = 1 - step;

    for(int i=G; i<=Vmax; i++)
        if(dp[step][i])
            ans = min(ans, dp[step][i]);

    cout << ans;
    return 0;
}