import Control.Monad
import Control.Monad.ST
import Data.Maybe
import qualified Data.ByteString.Char8 as BS
import Data.List
import qualified Data.Vector.Unboxed as VU
import qualified Data.Vector.Unboxed.Mutable as VUM

readInt = fst . fromJust . BS.readInt
readIntList = map readInt . BS.words
getInt = readInt <$> BS.getLine
getIntList = readIntList <$> BS.getLine
toTuple (x : y : _) = (x, y)

main = do
    [h, n] <- getIntList
    abs <- map toTuple <$> replicateM n getIntList
    let ans = runST $ do
            dp <- VUM.replicate 10001 (10 ^ 9)
            VUM.write dp 0 0
            forM_ abs $ \(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 $ min s (t + b)
            VU.freeze dp
    print . flip (VU.!) h $ VU.scanr min (10 ^ 9) ans