#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

const int WMAX = 5003, INFI = 2e9;
int D[WMAX];

int main () {

    freopen ("rucsac.in", "r", stdin);
    freopen ("rucsac.out", "w", stdout);
    int N, W, i, j, a, b;
    scanf ("%d%d", &N, &W);
    for (i = 1; i <= W; ++i)
        D[i] = INFI;
    for (i = 1; i <= N; ++i) {
        scanf ("%d%d", &a, &b);
        for (j = W; j >= a; --j)
            D[j] = min (D[j], D[j - a] + b);
    }
    printf ("%d", D[W]);

}