#include <bits/stdc++.h>
#define int long long

using namespace std;
const int maxn = 2e5 + 10;
int n, c, t[maxn], d[maxn];

/**
    Idea: Binary search the answer
    Conditions:
        - Total time needed <= total time allowed
        - Minimum effort on last day <= time for that day
**/

inline bool check(int val)
{
    int sum_effort = 0, last_day = 0;
    for (int i=1; i<=n; i++)
    {
        int num_days = min(val, (t[i] - 1) / d[i] + 1);
        int work = max(0ll, t[i] -  d[i] * num_days);
        sum_effort += num_days + work;
        if (num_days == val) last_day += work + 1;
    }
//    if (val == 11) cerr<<sum_effort<<" "<<last_day<<"\n";
    return (1.0 * sum_effort / val <= c && last_day <= c);
}

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cin>>n>>c;
    int mx = 0;
    for (int i=1; i<=n; i++) cin>>t[i]>>d[i], mx += (t[i]-1)/d[i] + 1;
    int lo = 1, hi = mx, ans = hi;
    while (lo <= hi)
    {
        int mid = (lo + hi) >> 1;
        if (check(mid)) ans = mid, hi = mid - 1;
        else lo = mid + 1;
    }
    cout<<ans - 1;
}