#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll INF = 4e18;
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
 
    int N, K;
    cin >> N >> K;
    vector<int> v(N);
    vector<ll> c(N);
    ll maxC = 0;
    for (int i = 0; i < N; i++) {
        cin >> v[i] >> c[i];
        maxC = max(maxC, c[i]);
    }
 
    auto can = [&](ll M) -> bool {
        static ll dp[5001];
        for (int i = 0; i <= 5000; i++) dp[i] = INF;
        dp[0] = 0;
 
        for (int i = 0; i < N; i++) {
            ll w = c[i] - (M + 1); // 핵심 수정!
            for (int val = 5000; val >= v[i]; val--) {
                if (dp[val - v[i]] != INF)
                    dp[val] = min(dp[val], dp[val - v[i]] + w);
            }
        }
        for (int val = K; val <= 5000; val++) {
            if (dp[val] < 0) return true; // "< 0" 조건
        }
        return false;
    };
 
    ll lo = 0, hi = maxC, ans = maxC;
    while (lo <= hi) {
        ll mid = (lo + hi) / 2;
        if (can(mid)) {
            ans = mid;
            hi = mid - 1;
        } else {
            lo = mid + 1;
        }
    }
    cout << ans << "\n";
}

I2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+CnVzaW5nIG5hbWVzcGFjZSBzdGQ7CnVzaW5nIGxsID0gbG9uZyBsb25nOwpjb25zdCBsbCBJTkYgPSA0ZTE4OwoKaW50IG1haW4oKSB7CiAgICBpb3M6OnN5bmNfd2l0aF9zdGRpbyhmYWxzZSk7CiAgICBjaW4udGllKG51bGxwdHIpOwoKICAgIGludCBOLCBLOwogICAgY2luID4+IE4gPj4gSzsKICAgIHZlY3RvcjxpbnQ+IHYoTik7CiAgICB2ZWN0b3I8bGw+IGMoTik7CiAgICBsbCBtYXhDID0gMDsKICAgIGZvciAoaW50IGkgPSAwOyBpIDwgTjsgaSsrKSB7CiAgICAgICAgY2luID4+IHZbaV0gPj4gY1tpXTsKICAgICAgICBtYXhDID0gbWF4KG1heEMsIGNbaV0pOwogICAgfQoKICAgIGF1dG8gY2FuID0gWyZdKGxsIE0pIC0+IGJvb2wgewogICAgICAgIHN0YXRpYyBsbCBkcFs1MDAxXTsKICAgICAgICBmb3IgKGludCBpID0gMDsgaSA8PSA1MDAwOyBpKyspIGRwW2ldID0gSU5GOwogICAgICAgIGRwWzBdID0gMDsKCiAgICAgICAgZm9yIChpbnQgaSA9IDA7IGkgPCBOOyBpKyspIHsKICAgICAgICAgICAgbGwgdyA9IGNbaV0gLSAoTSArIDEpOyAvLyDtlbXsi6wg7IiY7KCVIQogICAgICAgICAgICBmb3IgKGludCB2YWwgPSA1MDAwOyB2YWwgPj0gdltpXTsgdmFsLS0pIHsKICAgICAgICAgICAgICAgIGlmIChkcFt2YWwgLSB2W2ldXSAhPSBJTkYpCiAgICAgICAgICAgICAgICAgICAgZHBbdmFsXSA9IG1pbihkcFt2YWxdLCBkcFt2YWwgLSB2W2ldXSArIHcpOwogICAgICAgICAgICB9CiAgICAgICAgfQogICAgICAgIGZvciAoaW50IHZhbCA9IEs7IHZhbCA8PSA1MDAwOyB2YWwrKykgewogICAgICAgICAgICBpZiAoZHBbdmFsXSA8IDApIHJldHVybiB0cnVlOyAvLyAiPCAwIiDsobDqsbQKICAgICAgICB9CiAgICAgICAgcmV0dXJuIGZhbHNlOwogICAgfTsKCiAgICBsbCBsbyA9IDAsIGhpID0gbWF4QywgYW5zID0gbWF4QzsKICAgIHdoaWxlIChsbyA8PSBoaSkgewogICAgICAgIGxsIG1pZCA9IChsbyArIGhpKSAvIDI7CiAgICAgICAgaWYgKGNhbihtaWQpKSB7CiAgICAgICAgICAgIGFucyA9IG1pZDsKICAgICAgICAgICAgaGkgPSBtaWQgLSAxOwogICAgICAgIH0gZWxzZSB7CiAgICAgICAgICAgIGxvID0gbWlkICsgMTsKICAgICAgICB9CiAgICB9CiAgICBjb3V0IDw8IGFucyA8PCAiXG4iOwp9

NSAxMAoxIDEKMiAyCjMgMwo0IDQKNSA1

5 10
1 1
2 2
3 3
4 4
5 5