local n, k = io.read("*n", "*n")
local w, d = {}, {}
for i = 1, n do
  w[i], d[i] = io.read("*n", "*n")
end
local min, max = 0, 2
for i = 1, 6 do
  max = max * 1000
end

local function solve(x)
  local c = 0
  for i = 1, n do
    if w[i] <= x then
      c = c + (x - w[i]) // d[i] + 1
    end
  end
  return k <= c
end
if solve(min) then
  print(min)
else
  while 1 < max - min do
    local mid = (min + max) // 2
    if solve(mid) then
      max = mid
    else
      min = mid
    end
  end
  print(max)
end
