#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 cmp = [] (auto x, auto y) {
            if (x[1] == y[1]) return x[0] > y[0];
            return x[1] < y[1];
        };
        priority_queue<array<__int128_t, 2>, vector<array<__int128_t, 2>>, decltype(cmp)> pq(cmp);
        for (auto& t : tsk) pq.push({t[0], t[1]});
        
        __int128_t row = 0, col = 0;
        __int128_t fintim = 0;
        res++;
        while (pq.size()) {
            auto [t, d] = pq.top(); pq.pop();
            __int128_t rem = t % d;
            __int128_t need = t/d;
            
            if (col + need >= res) {
                fintim++;
                if (row == c-1) {
                    pq.push({t - d * (res - col), min(t - d * (res - col), d)});
                    col = res; ++row;
                    break;
                } else if (need > res) {
                    row++;
                    t -= (d * res);
                    fintim += t;
                } else {
                    // need <= res, and we can fit
                    if (rem) {
                        if (need == res) {
                            fintim += rem;
                            fintim--;
                            row++;
                        } else {
                            col += need; col -= res;
                            row++;
                            pq.push({rem, rem});
                        }
                    } else {
                        // no remainder
                        col += need; col -= res;
                        row++;
                    }
                }
            } else {
                col += need;
                if (rem) {
                    pq.push({rem, rem});
                }
            }
        }

        // cout << "-----\n";
        while (pq.size()) {
            auto [t, d] = pq.top(); pq.pop();
            fintim += t;
        }
        // cout << (ll)fintim << endl;
        return fintim <= 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;
    // for (int i = 3; i <= 3; ++i) {
    //     cerr << i << " " << can(i) << endl;
    // }
}

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

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