#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 = [&] (ll res) -> bool {
        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<__int128_t, 2>, vector<array<__int128_t, 2>>, decltype(cmp1)> todo(cmp1);
        priority_queue<array<__int128_t, 2>, vector<array<__int128_t, 2>>, decltype(cmp2)> tokill(cmp2);
        for (auto& x : tsk) todo.push({x[0], x[1]});
        int cando = min(n, c);

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

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

    ll l = 0, r = 1e16;
    while (l < r) {
        ll 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();
}