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

int n, c;
pair<int, int> arr[200001];

long long s[200001];
int tmp[200001];

int check(long long threshold) {
    priority_queue<pair<int, int>> tasks;
    for (int i = 1; i <= n; ++i) {
        tasks.emplace(arr[i].first, i);
        tmp[i] = arr[i].first;
        s[i] = -1;
    }

    priority_queue<pair<long long, int>> pq;
    for (int i = 1; i <= min(c, n); ++i) {
        int idx = tasks.top().second;
        s[idx] = 0;
        pq.emplace(-(arr[idx].second / arr[idx].first), idx);
        tasks.pop();
    }

    long long r = 0;

    while (!pq.empty() && r <= threshold) {
        long long next_r = -pq.top().first;
        int idx = pq.top().second;
        long long diff = next_r - r;
        pq.pop();
        if (next_r > threshold) {
            break;
        }
        if (tmp[idx] >= arr[idx].first) {
            tmp[idx] %= arr[idx].first;
            tasks.emplace(tmp[idx], idx);
        } else {
            tmp[idx] = 0;
        }

        while (!tasks.empty() && pq.size() <= c) {
            int d = tasks.top().first;
            int target = tasks.top().second;
            tasks.pop();
            if (s[target] == -1)
                s[target] = next_r;
            pq.emplace(-(tmp[target] / d + next_r), target);
        }
        r = next_r;
    }

    long long v = 0;
    for (int i = 1; i <= n; ++i) {
        if (s[i] == -1)
            v += tmp[i];
        if (!tmp[i])
            continue;

        long long d = threshold - s[i] + 1;
        long long decr = d * arr[i].first;
        v += max(1LL, arr[i].second - decr + 1);
    }

    return v <= c;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> c;
    for (int i = 1; i <= n; ++i) {
        int t, d;
        cin >> t >> d;
        arr[i] = {d, t};
    }

    long long low = 0, high = 1'000'000'000'000'000'101;

    while (low < high) {
        long long mid = low + high >> 1;
        if (check(mid))
            high = mid;
        else
            low = mid + 1;
    }
    cout << low;

}