#include <bits/stdc++.h>
//#pragma GCC optimize("O3,unroll-loops")
//#pragma GCC target("avx2,bmi,bmi2,popcnt,lzcnt")


using namespace std;

ifstream fin("energii.in");
ofstream fout("energii.out");

using dbl = double;
using ll = long long;
using ull = unsigned long long;

const int nmax = 1e5 + 1;
const int mod = 1e9 + 7;

int n,w;
vector<pair<int,int>> e;
vector<ll> dp(5001,INT_MAX);
int main() {
    fin >> n >> w;
    e.resize(n);
    for (auto& p : e)
        fin >> p.first >> p.second;
    dp[0] = 0;
    for (auto p : e) {
        const int x = p.first, y = p.second;
        for (int i = w; i >= 0; i--) {
            if (i + x <= w) {
                dp[i + x] = min(dp[i + x], dp[i] + y);
            }
        }
    }
    fout << dp[w];

    return 0;
}