#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;
  ll maxlen = 0, totallen = 0;
  REP(i,0,n) {
    cin >> t[i] >> d[i];
    q[i] = t[i] / d[i];
    r[i] = t[i] % d[i];
    ll len = q[i] + (r[i] > 0 ? 1 : 0);
    maxlen = max(maxlen, len);
    totallen += len;
    oT += t[i];
  }
  ll Dl = 1, Dr = max(maxlen, (totallen + C - 1) / C);
  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;
}