#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <string>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <sstream>
#include <complex>
#include <ctime>
#include <cassert>
#include <functional>

using namespace std;

typedef long long ll;
typedef vector<int> VI;
typedef pair<int,int> PII;

#define REP(i,s,t) for(int i=(s);i<(t);i++)
#define FILL(x,v) memset(x,v,sizeof(x))

const int INF = (int)1E9;
#define MAXN 200005

int t[MAXN], d[MAXN], q[MAXN], r[MAXN];
int main() {
  int n;
  ll C, oT = 0;
  cin >> n >> C;
  REP(i,0,n) {
    cin >> t[i] >> d[i];
    q[i] = t[i] / d[i];
    r[i] = t[i] % d[i];
    oT += t[i];
  }
  if (C >= n) {
    ll Dl = 1, Dr = INF;
    while (Dl <= Dr) {
      ll D = (Dl + Dr) / 2;
      ll T = oT;
      int full = 0;
      REP(i,0,n) {
        T -= min(D, (ll)q[i]) * d[i];
        if (q[i] < D) T -= r[i];
        int need = q[i] + (r[i] > 0 ? 1 : 0);
        if (need >= D) full++;
      }
      if (T <= C - full) Dr = D - 1;
      else Dl = D + 1;
    }
    cout << Dl - 1 << endl;
  } else {
    ll total = 0, maxlen = 0;
    REP(i,0,n) {
      int cur = (t[i] + d[i] - 1) / d[i];
      total += cur;
      maxlen = max(maxlen, (ll)cur);
    }
    if ((total + C - 1) / C > maxlen) {
      cout << (total + C - 1) / C - 1 << endl;
    } else {
      ll Dl = 1, Dr = maxlen;
      while (Dl <= Dr) {
        ll D = (Dl + Dr) / 2;
        ll T = 0, slots = 0;
        int full = 0;
        REP(i,0,n) {
          int need = q[i] + (r[i] > 0 ? 1 : 0);
          if (need >= D) {
            T += max(0ll, t[i] - D * d[i]);
            full++;
          } else slots += need;
        }
        ll availSlots = (D - 1) * (C - full) + max(0ll, C - full - T);
        if (availSlots >= slots && full + T <= C) Dr = D - 1;
        else Dl = D + 1;
      }
      cout << Dl - 1 << endl;
    }
  }
  return 0;
}