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

import qualified Data.Vector.Unboxed as VU
import qualified Data.Vector.Unboxed.Mutable as VUM

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 = runST $ do
        dp <- VUM.replicate 10001 (10 ^ 9) :: ST s (VUM.MVector s Int)

        VUM.write dp 0 0

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

              VUM.write dp i $ minimum [s, t + b']

        VU.freeze dp

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

  return ()
