//0026
#include <cstdio>
#include <cstdlib>
#include <algorithm>

using namespace std;

int main() {
    FILE* fi = fopen("energii.in", "rt");
    FILE* fo = fopen("energii.out", "wt");

    int g,w;
    fscanf(fi, "%d%d", &g, &w);

    int* eg = (int*)malloc(g * sizeof(int));
    int *cg = (int*)malloc(g * sizeof(int));
    int** c = (int**)malloc(g * sizeof(int*));
    for (int i = 0; i < g; i++)
        c[i] = (int*)malloc((w + 1) * sizeof(int));

    for (int i = 0; i < g; i++)
        fscanf(fi, "%d%d", &eg[i], &cg[i]);

    c[0][0] = 0;
    for (int i = 1; i <= w; i++)
        c[0][i] = 20010;

    for (int i = 0; i < g; i++) {
        for (int j = 0; j <= min(w, eg[i]); j++)
            c[i + 1][j] = c[i][j];
        for (int j = 0; j <= w - eg[i]; j++)
            c[i + 1][j + eg[i]] = min(c[i][j + eg[i]], c[i][j] + cg[i]);
        int m = 20010;
        for (int j = max(0, w - eg[i]); j <= w; j++)
            if (m < c[i][j])
                m = c[i][j];
        c[i + 1][w] = min(c[i][w], m + cg[i]);
    }

    return 0;
}