#include <bits/stdc++.h>

using namespace std;

const int INF = 0X3f3f3f3f;
const int N_MAX = 1002;
const int W_MAX = 5002;

int n, w;
int dp[N_MAX][W_MAX];
vector <int> energies, costs;

void read() {
    ifstream fin("energii.in");

    fin >> n >> w;

    energies.resize(n + 1); costs.resize(n + 1);
    for (int i = 1; i <= n; ++i) {
        fin >> energies[i] >> costs[i];
    }

    fin.close();
}

void solve() {
    for (int i = 0; i <= n; ++i) {
        for (int j = 1; j <= w; ++j) {
            dp[i][j] = INF;
        }
    }

    for(int i = 1; i <= n; ++i) {
        for(int j = 1; j <= w; ++j) {
            if(energies[i] > j) {
                dp[i][j]=min(dp[i - 1][j], costs[i]);
            } else {
                dp[i][j]=min(dp[i - 1][j], dp[i - 1][j - energies[i]] + costs[i]);
            }
        }
    }
}

void write() {
    ofstream fout("energii.out");

    fout << dp[n][w];

    fout.close();
}

int main() {
    read();
    solve();
    write();
    return 0;
}