#include <fstream>

using namespace std;
ifstream fin("energii.in");
ofstream fout("energii.out");
int n, g, v[1001], G[1001], dp[100000001], mx, g1;
int main()
{
    fin >> n >> g;
    for (int i = 1; i <= n; i++)
    {
        fin >> G[i] >> v[i];
        mx += G[i];
    }
    for (int i = 0; i <= mx; i++)
    {
        dp[i] = -1;
    }
    dp[0] = 0;
    for (int i = 1; i <= n; i++)
    {
        for (int cg = mx - G[i]; cg >= 0; cg--)
        {
            if (dp[cg + G[i]] < 1 && cg <= i)
            {
                if (dp[cg] != -1)
                {
                    dp[cg + G[i]] = dp[cg] + v[i];
                }
            }
            if (dp[cg] != -1)
            {
                dp[cg + G[i]] = min(dp[cg + G[i]], (dp[cg] + v[i]));
            }
        }
    }
    int fin = 10000000;
    for (int i = g; i <= mx; i++)
    {
        if (dp[i] > 0)
            if (max(dp[i], fin) == fin)
            {
                fin = dp[i];
                g1 = i;
            }
    }
    fout << fin;
    return 0;
}