{-# LANGUAGE BangPatterns #-}
import qualified Data.ByteString.Char8 as B
import qualified Data.Vector.Unboxed as VU
import Data.Char
import Control.Monad

solve :: Int ->  VU.Vector (Int,Int) -> VU.Vector Int
solve !h !abs = VU.foldl' step (VU.singleton 0) (VU.generate h $ \i -> i + 1)
    where
        step :: VU.Vector Int -> Int -> VU.Vector Int
        step !v !i =  
            let
                m = VU.foldl' (\ !x (!a,!b) -> let !y = if i >= a then b + (v VU.! (i-a)) else b in min x y) (10^9) abs
            in
                VU.generate (i+1) $ \ !j -> if j == i then m else v VU.! j 
    

main = do
    [h, n] <- map  read . words <$> getLine :: IO [Int]
    abs <- VU.replicateM n $ do 
        s <- B.getLine 
        let Just (a, s') = B.readInt s
        let Just (b, _) = B.readInt $ B.dropWhile isSpace s'
        return (a,b)
    print $ VU.last $ solve h abs