#include <queue>
#include <vector>
#include <iostream>
#include <algorithm>

using namespace std;

typedef long long ll;

pair<ll, ll> td[200001];
ll n, c;

bool finish(ll k) {
    priority_queue<vector<ll> > que;
    ll researches = min(n,c)*(k+1);
    ll last_day_research = 0;
    int i = 0;
    ll todo = 0;
    while(!que.empty() || i < n) {
        if (i < n) {
            ll t = td[i].first, d = td[i].second;
            if (!que.empty() && que.top()[0] >= d) {
                if (researches) {
                    researches--;
                    last_day_research += que.top()[2];
                }
                else todo += que.top()[0];
                todo += que.top()[1];
                que.pop();
            } else {
                ll research = min({t / d, k, researches});
                researches -= research;
                
                ll remain = t - research * d;
                
                if (remain) {
                    if (remain > d) {
                        vector<ll> tmp = {d, remain - d, research == k};
                        que.emplace(tmp);
                    } else {
                        vector<ll> tmp = {remain, 0, research == k};
                        que.emplace(tmp);
                    }
                }
                i++;
            }
        } else {
            if (researches) {
                researches--;    
                last_day_research += que.top()[2];
            }
            else todo += que.top()[0];
            todo += que.top()[1];
            que.pop();
        }
    }
    if (last_day_research > min(n, c)) return false;
    
    return  max({(ll)0, last_day_research, min(n,c) - researches}) + todo <= c;
}

bool comp(pair<ll,ll> x, pair<ll,ll> y) {
    return x.second > y.second;
}

int main ()
{
    cin >> n >> c;

    ll max_k = 0;
    for (int i = 0; i < n; i++) {
        ll t, d;
        scanf("%lld %lld", &t, &d);
        td[i] = pair<ll,ll>(t, d);
        max_k = max(max_k, (t+d-1)/d);
    }
    sort(td, td+n, comp);
    
    ll l = 0, r = max_k * n / min(c,n) + 5;
    while (l <= r) {
        ll m = l + (r-l)/2;
        if (finish(m)) r = m - 1;
        else l = m + 1;
    }
    cout << l << endl;
    
    return 0;
}