#include <iostream>
#include <fstream>
#define dimn 1005
#define dimw 5005

std::ifstream f("energii.in");
std::ofstream g("energii.out");

int G, W;
int cant[dimn], cost[dimn];
int sol = 1e9;

int knapsack[dimn][dimw];
void calc_knapsack() {
    knapsack[0][cant[0]] = cost[0];

    for (int i=1, j, l, k; i<G; i++) {
        knapsack[i-1][0] = 0;

        for (k=0; k<W; k++)

            if(knapsack[i-1][k]) {
                knapsack[i][k] = knapsack[i-1][k];

                if(k + cant[i] < W) {
                    if(knapsack[i][k+cant[i]] == 0)
                        knapsack[i][k+cant[i]] = knapsack[i-1][k] + cost[i];
                    else if(knapsack[i][k+cant[i]] > knapsack[i-1][k] + cost[i])
                        knapsack[i][k+cant[i]] = knapsack[i-1][k] + cost[i];
                }

                else sol = std::min(sol, knapsack[i-1][j] + cost[i]);
            }
    }
}

void citire() {
    f >> G >> W;
    for (int i=0; i<G; i++)
        f >> cant[i] >> cost[i];
}
void rezolvare() {
    calc_knapsack();
    g << sol;
}

int main()
{
    citire();
    rezolvare();

    return 0;
}