{-# LANGUAGE BangPatterns #-}
import Control.Arrow (second)
import Control.Monad
import Control.Monad.Fix
import Data.List (foldl')
import qualified Data.Vector.Unboxed as VU
import qualified Data.ByteString.Char8 as B
import System.IO.Unsafe
import Debug.Trace

solve :: Int -> Int -> VU.Vector (Int,Int) -> Int
solve !n !k !wds = nearest $ let i = findInternal 1 in search i (2*i) where
  calc !t = VU.sum $ VU.map (\(w,d) -> if t > w then (t-w) `div` d + 1 else 0) wds
  nearest !t = VU.maximum $ VU.map (\(w,d) -> w + ((t-w) `div` d) * d) wds

  findInternal !t = last $ takeWhile (\t -> calc t < k) $ map (\k -> 2^k) [0..]
  
  search !a !b =
    let c = (a + b) `div` 2
        u = calc c
    in
      if u == k then c
      else if u < k then search (c-1) b
      else search a (c+1)

main = do
  let readInt = fmap (second B.tail) . B.readInt

  nk <- VU.unfoldrN 2 readInt <$> B.getLine
  wds <- VU.replicateM (nk VU.! 0) ((\vec -> (vec VU.! 0, vec VU.! 1)) . VU.unfoldrN 2 readInt <$> B.getLine)
  print $ solve (nk VU.! 0) (nk VU.! 1) wds
