import           Control.Monad
import qualified Data.ByteString.Char8       as BS
import           Data.Maybe
import qualified Data.Vector.Unboxed         as V
import qualified Data.Vector.Unboxed.Mutable as VM

readInt = fst . fromJust . BS.readInt
readIntList = map readInt . BS.words
getInt = readInt <$> BS.getLine
getIntList = readIntList <$> BS.getLine

main = do
  [h, n] <- getIntList
  abs <- V.replicateM n $ do
    [a, b] <- getIntList
    return (a, b)

  let inf = 10^9 :: Int

  -- dp[decreased hp] == minimum mp to achieve it                                                                                              dp <- VM.new (h+1)
  VM.set dp inf
  VM.write dp 0 (0::Int)

  forM_ [0..(h-1)] $ \i -> do
    mp0 <- VM.read dp i
    when (mp0 < inf) $ do
      forM_ [0..(n-1)] $ \j -> do
        let (a,b) = abs V.! j
            hp1 = min h (i+a)
            mp1 = mp0 + b
        mp1' <- VM.read dp hp1
        VM.write dp hp1 (min mp1 mp1')

  ans <- VM.read dp h
  print ans