#!/usr/bin/env python3

def can(l, timeinday, numdays):
  free = 0
  nontrivial = []
  for (t, d) in l:
    need = (t + d - 1) // d
    if need > numdays:
      nontrivial.append((t, d))
    else:
      free += need
  timelast = 0
  for (t, d) in nontrivial:
    t -= d * (numdays+1)
    timelast += max(0, t) + 1
  if len(nontrivial) > timeinday:
    return False
  if free > numdays * (timeinday - len(nontrivial)) + max(0, timeinday - timelast):
    return False
  return timelast <= timeinday

def solve():
  n, k = (int(x) for x in input().split())
  l = []
  for _ in range(n):
    l.append([int(x) for x in input().split()])
  lhs = 0
  rhs = 10 ** 18
  while lhs < rhs:
    mid = (lhs + rhs) // 2
    if can(l, k, mid):
      rhs = mid
    else:
      lhs = mid + 1
  print(lhs)

solve()