import qualified Data.Text as T
import qualified Data.Text.IO as T
import qualified Data.Text.Read as T
import Data.List (sortBy)

main :: IO ()
main = do
  (h : n : _) <- map unsafeSignedDecimal . T.words <$> T.getLine :: IO [Int]
  abs <- sequence . replicate n $ unsafeListToTuple . map unsafeSignedDecimal . T.words <$> T.getLine :: IO [(Int, Int)]
  let
    abs' = sortBy cmp abs
      where
        cmp (a, b) (a', b') = compare (b * a') (a * b')
    (_, _, s) = foldl step (h, 0, 10 ^ 8) $ abs'
      where
        step acc@(0, _, _) _ = acc
        step (u, v, w) (a, b) = (u', v', min w w')
          where
            (q, r) = u `divMod` a
            u' = u - q * a
            v' = v + q * b
            w' | r == 0    = v'
               | otherwise = v' + b
  print s

unsafeListToTuple :: [Int] -> (Int, Int)
unsafeListToTuple (x : y : _) = (x, y)

unsafeSignedDecimal :: T.Text -> Int
unsafeSignedDecimal s = case T.signed T.decimal s of
  Right (n, _) -> n
