import Data.Maybe
import qualified Data.ByteString.Char8 as BS
import Data.List
import Data.Int
import Control.Monad
import Control.Monad.ST
import qualified Data.Array.IArray as Array
import Data.Array.MArray
import Data.Array.ST

getInts :: IO [Int]
getInts = map (fst . fromJust . BS.readInt) . BS.words <$> BS.getLine

main :: IO ()
main = do
  [h, n] <- getInts :: IO [Int]
  [a, b] <- transpose <$> replicateM n getInts

  
  let ans = runSTUArray $ do
        dp <- newArray (0, 10000) (10 ^ 9) :: ST s (STUArray s Int Int)

        writeArray dp 0 0

        forM_ (zip a b) $ \(a', b') -> do
          forM_ [0..10000] $ \i -> do
            when (i - a' >= 0) $ do
              s <- readArray dp i
              t <- readArray dp (i - a')

              writeArray dp i $ minimum [s, t + b']
        
        return dp

  print $ (!! h) $ scanr min (10 ^ 9) (Array.elems ans)

  return ()
