#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

void solve() {
    int n, c; cin >> n >> c;
    vector<array<ll, 2>> tsk;
    for (int i = 0; i < n; ++i) {
        int t, d; cin >> t >> d;
        tsk.push_back({t, d});
    }

    auto can = [&] (int res) -> bool {
        // cerr << "------------------------\nGuess: " << res << "\n";
        auto cmp1 = [] (auto& x, auto& y) {
            return x[1] < y[1];
        };
        auto cmp2 = [] (auto& x, auto& y) {
            return x[0] / x[1] > y[0] / y[1];
        };
        priority_queue<array<ll, 2>, vector<array<ll, 2>>, decltype(cmp1)> todo(cmp1);
        priority_queue<array<ll, 2>, vector<array<ll, 2>>, decltype(cmp2)> tokill(cmp2);
        for (auto& x : tsk) todo.push(x);
        int cando = min(n, c);

        ll time = 0;
        vector<array<ll, 2>> remaining;
        while (todo.size() || tokill.size()) {   
            while (tokill.size() < cando && todo.size()) {
                auto [x, y] = todo.top(); todo.pop();
                // cerr << "push " << x << " " << y << " at time " << time << endl;
                tokill.push({x + y*time, y});
            }
            auto [t, d] = tokill.top(); tokill.pop();
            // cerr << "pop " << t << " " << d << endl;
            if (t / d > res) {
                // cerr << "too big" << endl;
                time = res;
                remaining.push_back({t-d*res, d});
            } else {
                time = t/d;
                ll rem = t % d;
                // cerr << "rem " << rem << endl;
                if (rem != 0) {
                    // cerr << "pushing to todo" << endl;
                    todo.push({rem, rem});
                }
            }
            // cerr << "todo size: " << todo.size() << endl;
        }

        ll finaltime = 0;
        for (auto [t, d] : remaining) {
            // cerr << "final: " << t << " " << d << endl;
            finaltime += t - d + 1;
        }
        return finaltime <= c;
    };

    int l = 0, r = 1e9;
    while (l < r) {
        int m = l + (r - l) / 2;
        if (can(m)) r = m;
        else l = m + 1;
    }
    cout << l << endl;
}

int main() {
    cin.tie(0);
    cin.sync_with_stdio(0);

	int t = 1;
    // cin >> t;
	while (t--) solve();
}