-- [Char]あるいは String を Int にする
toInt :: (String -> Int)
toInt x = read x ::Int

--入力を受け取り、[Int]にする
getInts = do
  x <- getLine
  let y = (map$toInt)$words x -- 半角スペースで分割してInt にする
  return y

getMat :: (Int -> IO [[Int]])
getMat 1 = do
  y <- getInts
  return [y]
getMat x = do
  y <- getInts
  z <- getMat (x-1)
  let w = [y] ++ z
  return w


main = do 
  hn <- getLine
  let h = (read . head . words $ hn) :: Int
  let n = (read . (!! 1) . words $ hn) :: Int
  ab <- getMat n
  putStrLn $ show (solve h ab)

solve :: Int -> [[Int]] -> Int
solve h ab = gdm * nn + l
  where
  gd = ab !! gdpf 0 0 [0,1] ab
  gdm = gd !! 1
  nn = div h (gd !! 0)
  mm = mod h (gd !! 0)
  l = lsts 0 mm gdm ab

gdpf :: Int -> Int -> [Int] -> [[Int]] -> Int
gdpf i j _ [] = j
gdpf i j m ab@(iab:abz)
  |(iab!!0)*(m!!1) > (m!!0)*(iab!!1) = gdpf (i+1) i iab abz
  |otherwise                         = gdpf (i+1) j m abz

lsts :: Int -> Int -> Int -> [[Int]] -> Int
lsts _ _ mn [] = mn
lsts i h mn ab@(iab:abz)
  |iab!!0 >= h && iab!!1 < mn = lsts (i+1) h (iab!!1) abz
  |otherwise                  = lsts (i+1) h mn  abz

