#include <fstream>
#include <cstring>

constexpr int MAX_N = 1001;
constexpr int MAX_W = 5000 * 1000 + 1;

int cost[MAX_W];
int w[MAX_W];
int c[MAX_N];

int main() {
    int n, req, i, j, C = 0, W = 0;
    std::ifstream in("energii.in");
    std::ofstream out("energii.out");
    in >> n >> req;
    for (i = 0; i < n; ++i) {
        in >> w[i] >> c[i];
        W += w[i];
        C += c[i];
    }
    for (i = 0; i < n; ++i) {
        for (j = w[i]; j <= W; ++j) if (c[i] + cost[j] > cost[j - w[i]]) cost[j - w[i]] = c[i] + cost[j];
    }
    out << (C - cost[req]);
    return 0;
}