#include <iostream>
#include <fstream>

#define GMAX 1001
#define WMAX 5001
#define INF (1 << 30)

#define MIN(a, b) (a < b) ? a : b

using namespace std;

int C[GMAX][WMAX];

int main()
{
    int g, w;
    int eg[GMAX], cg[GMAX];

    // open files
    freopen("energii.in", "r", stdin);
    freopen("energii.out", "w", stdout);

    // read input
    cin >> g >> w;

    for (int i = 0; i < g; i++)
    {
        cin >> eg[i] >> cg[i];
    }

    // solve
    for (int i = 1; i <= w; i++)
    {
        C[0][i] = INF;
    }

    for (int i = 1; i <= g; i++)
    {
        for (int j = 1; j <= w; j++)
        {
            if (eg[i - 1] >= j)
            {
                C[i][j] = MIN(cg[i - 1], C[i - 1][j]);
                //cout << '!';
            }
            else
            {
                //cout << '?';
                C[i][j] = MIN(C[i - 1][j - eg[i - 1]] + cg[i - 1], C[i - 1][j]);
            }
            //cout << C[i][j] << ' ';
        }
        cout << endl;
    }

    // write output
    cout << C[g][w];

    return 0;
}