let rec lower_bound l r p =
  if r <= 1 + l
  then r
  else let m = (l + r) / 2 in
       if p m
       then lower_bound l m p
       else lower_bound m r p

let () = Scanf.scanf "%d %d\n" @@ fun n k ->
  let wds = Array.init n @@ fun _ ->
    Scanf.scanf "%d %d\n" @@ fun w d -> w, d in
  Printf.printf "%d\n" @@ lower_bound 0 (1 lsl 61) @@ fun x ->
    ( <= ) k @@ Array.fold_right (fun (w, d) -> ( + ) @@
      if x < w then 0
      else 1 + (x - w) / d) wds 0
