{-# LANGUAGE MultiWayIf #-}

module Main where

import           Control.Monad
import qualified Data.Array                    as A
import qualified Data.Array.IO                 as AIO
import qualified Data.Array.Unboxed            as AU
import qualified Data.ByteString               as BS
import qualified Data.ByteString.Char8         as BSC8
import           Data.Char
import           Data.List
import qualified Data.Map.Strict               as M
import           Data.Maybe
import           Data.Ord
import qualified Data.Set                      as S
import qualified Data.Vector                   as V
--import           Data.Vector.Algorithms.Search
import qualified Data.Vector.Mutable           as VM
import qualified Data.Vector.Unboxed           as VU
import qualified Data.Vector.Unboxed.Mutable   as VUM
import           Debug.Trace
--import qualified Data.Heap                     as H
main = do
  [iH, iN] <- getIL
  ab       <- VU.fromList <$> replicateM iN getIT2
  let dpSize = iH + (fst $ VU.maximumBy (comparing fst) ab) + 1
  let maxValue = 10 ^ 8 * iN + 1
  dp       <- VUM.replicate (dpSize + 1) maxValue :: IO (VUM.IOVector Int)
  minValue <- doDP dp ab dpSize iH maxValue
  print minValue

doDP :: VUM.IOVector Int -> VU.Vector (Int, Int) -> Int -> Int -> Int -> IO Int
doDP dp vecVV dpSize mark maxValue = do
  VUM.write dp 0 0
  VU.forM_ vecVV $ \(volume, value) -> forM_ [1 .. dpSize] $ \dpIndex ->
    if dpIndex - volume >= 0
      then do
        indexValue <- VUM.read dp dpIndex :: IO Int
        prevValue  <- VUM.read dp (dpIndex - volume)
        let newDP = min indexValue (prevValue + value)
        VUM.write dp dpIndex newDP
        if dpIndex >= mark then return newDP else return maxValue
      else return maxValue
  foldM
    (\acc x -> do
      target <- VUM.read dp x
      return (min target acc)
    )
    maxValue
    [mark .. dpSize]

getVUI :: IO (VU.Vector Int)
getVUI = VU.unfoldr (BSC8.readInt . BSC8.dropWhile isSpace) <$> BSC8.getLine

getRepVUI :: Int -> IO (VU.Vector Int)
getRepVUI n =
  VU.unfoldr (BSC8.readInt . BSC8.dropWhile isSpace)
    .   BSC8.unlines
    <$> replicateM n BSC8.getLine

getVS :: IO (V.Vector Char)
getVS = V.fromList <$> getLine

getVUS :: IO (VU.Vector Char)
getVUS = VU.fromList <$> getLine

readI :: BSC8.ByteString -> Int
readI = fst . fromJust . BSC8.readInt

readIL :: BSC8.ByteString -> [Int]
readIL = map readI . BSC8.words

readIT2 :: BSC8.ByteString -> (Int, Int)
readIT2 bs =
  let words = BSC8.words bs in (readI $ head words, readI $ last words)

getI :: IO Int
getI = readI <$> BSC8.getLine

getIL :: IO [Int]
getIL = readIL <$> BSC8.getLine

getIT2 :: IO (Int, Int)
getIT2 = readIT2 <$> BSC8.getLine

getIT2Order :: IO (Int, Int)
getIT2Order =
  getIL >>= \x@[xz, xo] -> if xz > xo then return (xo, xz) else return (xz, xo)

getNIS :: Int -> IO [(Int, BSC8.ByteString)]
getNIS 0 = return []
getNIS n = do
  [aFst, aSnd] <- BSC8.words <$> BSC8.getLine
  next         <- getNIS (n - 1)
  return ((readI aFst, aSnd) : next)

il2Words :: [Int] -> String
il2Words = unwords . map show

il2Lines :: [Int] -> String
il2Lines = unlines . map show

p :: Int -> Int
p x = x - 1

--modNum = 10 ^ 9 + 7
modulus = 1000000007

newtype MInt = M Int

instance Num MInt where
  (M a) + (M b) = M $ mod (a + b) modulus

  (M a) - (M b) = M (a - b)

  (M a) * (M b) = M $ mod (a * b) modulus

  fromInteger a = M $ mod (fromInteger a) modulus

  abs (M a) = M $ abs a

  signum (M a) = M $ signum a

instance Show MInt where
  show (M a) = show (mod a modulus)

int2MInt :: Int -> MInt
int2MInt a = M (mod a modulus)

mInt2Int :: MInt -> Int
mInt2Int (M a) = a

{-
factsMod :: V.Vector MInt
factsMod = V.scanl (\acc x -> M x * acc) 1 $ V.generate 2000000 (+ 1)

factMod :: Int -> MInt
factMod = (factsMod V.!)
-}

factMod :: Int -> MInt
factMod n | n == 0    = 1
          | n == 1    = 1
          | otherwise = M n * (factMod (n - 1))


factDivMod :: Int -> Int -> MInt
factDivMod n k | n == k    = M 1
               | otherwise = M n * (factDivMod (n - 1) k)

powMod :: MInt -> Int -> MInt
powMod n k | k == 0       = M 1
           | k == 1       = n
           | mod k 2 == 0 = powMod (n ^ 2) (div k 2)
           | otherwise    = n * powMod (n ^ 2) (div k 2)

invMod :: MInt -> MInt
invMod (M 0) = error "inverse of 0"
invMod x     = powMod x (modulus - 2)

{-
combiMod :: Int -> Int -> MInt
combiMod n k
  | n < 0 || k < 0 || k > n = 0
  | otherwise = factMod n * invMod (factMod (n - k)) * invMod (factMod k)
-}
combiMod :: Int -> Int -> MInt
combiMod n k | n < 0 || k < 0 || k > n = 0
             | k > n - k = factDivMod n k * invMod (factMod (n - k))
             | otherwise = factDivMod n (n - k) * invMod (factMod k)



combi :: Int -> Int -> Int
combi n k | n < 0 || k < 0 || k > n = 0
          | k == n                  = 1
          | otherwise               = div (div (fact n) (fact (n - k))) (fact k)

primes :: V.Vector MInt
primes = V.scanl (\acc x -> M x * acc) 1 $ V.generate 200000 (+ 1)

fact :: Int -> Int
fact 0         = 1
fact n | n > 0 = n * fact (n - 1)

knappsackMaxVal
  :: AIO.IOArray (Int, Int) Int
  -> VU.Vector Int
  -> VU.Vector Int
  -> Int
  -> IO Int
knappsackMaxVal dp volumeVec valueVec dpSize = do
  mapM_
    (\i -> mapM_
      (\v -> do
        let volume = volumeVec VU.! i
            value  = valueVec VU.! i
        newdp <- if v < volume
          then AIO.readArray dp (i, v)
          else do
            dpIVm <- AIO.readArray dp (i, v - volume)
            dpIV  <- AIO.readArray dp (i, v)
            return (max (dpIVm + value) dpIV)
        AIO.writeArray dp (i + 1, v) newdp
      )
      [0 .. dpSize]
    )
    [0 .. VU.length volumeVec - 1]
  AIO.readArray dp (VU.length volumeVec, dpSize)

knappsackMinVol
  :: AIO.IOArray (Int, Int) Int
  -> VU.Vector Int
  -> VU.Vector Int
  -> Int
  -> Int
  -> IO Int
knappsackMinVol dp volumeVec valueVec dpSize maxVolume = do
  mapM_
    (\i -> mapM_
      (\v -> do
        let volume = volumeVec VU.! i
            value  = valueVec VU.! i
        newdp <- if (v + value) > dpSize
          then AIO.readArray dp (i, v)
          else do
            dpIVm <- AIO.readArray dp (i, v + value)
            dpIV  <- AIO.readArray dp (i, v)
            return (min (dpIVm - volume) dpIV)
        AIO.writeArray dp (i + 1, v) newdp
      )
      (reverse [0 .. dpSize])
    )
    [0 .. VU.length valueVec - 1]
  foldM
    (\acc x -> do
      num <- AIO.readArray dp (VU.length volumeVec, x)
      return $ if num <= maxVolume then x else acc
    )
    0
    [0 .. dpSize]


{-
hMaxPoint :: Int
hMaxPoint = 100
hMaximum :: H.Heap Int -> Int
hMaximum h = hMaxPoint - (H.minimum h)
hInsertMax :: Int -> H.Heap Int -> H.Heap Int
hInsertMax x = H.insert (hMaxPoint - x)
hDeleteMax :: H.Heap Int -> H.Heap Int
hDeleteMax = H.deleteMin
-}

myFilter :: (a -> Bool) -> [a] -> ([a], [a])
myFilter _pred [] = ([], [])
myFilter pred (x : xs)
  | pred x    = let (l, r) = myFilter pred xs in (x : l, r)
  | otherwise = let (l, r) = myFilter pred xs in (l, x : r)

--UnionFindデータ構造
type UF = (VUM.IOVector Int, VUM.IOVector Int)
uf_makeSet :: Int -> IO UF
uf_makeSet n = do
  parent <- VU.thaw $ VU.generate n id
  rank   <- VUM.replicate n 0
  return (parent, rank)
uf_union :: UF -> Int -> Int -> IO ()
uf_union unionFind@(parents, ranks) x y = do
  xRoot     <- uf_find unionFind x
  yRoot     <- uf_find unionFind y
  xRootRank <- VUM.read ranks x
  yRootRank <- VUM.read ranks y
  if
    | xRootRank > yRootRank -> VUM.write parents yRoot xRoot
    | xRootRank < yRootRank -> VUM.write parents yRoot xRoot
    | xRoot /= yRoot -> do
      VUM.write parents yRoot xRoot
      VUM.write ranks xRoot (xRootRank + 1)
    | otherwise -> return ()
uf_find :: UF -> Int -> IO Int
uf_find unionFind@(parents, ranks) x = do
  xParent <- VUM.read parents x
  if xParent == x
    then return x
    else do
      xRootParent <- uf_find unionFind xParent
      VUM.write parents x xRootParent
      return xRootParent

--UnDirectedGraph(無向グラフ)データ構造
type UDG = M.Map Int [Int]
list2UDG :: [(Int, Int)] -> M.Map Int [Int]
list2UDG = foldl
  (\acc x ->
    let lr = M.insertWith (++) (fst x) [snd x] acc
    in  M.insertWith (++) (snd x) [fst x] lr
  )
  M.empty


Measured memory_bytes: 2556