import Control.Monad
import Control.Monad.ST
import Data.Maybe
import Data.List
import qualified Data.Vector as V
import qualified Data.Vector.Mutable as MV
import qualified Data.ByteString.Char8 as BS

main = do
  h: n: _ <- map readAsInt . BS.words <$> BS.getLine :: IO [Int]
  xs <- map (map readAsInt . BS.words) <$> BS.lines <$> BS.getContents :: IO [[Int]]
  putStrLn $ show $ knapsack xs h

readAsInt = fst . fromJust . BS.readInt

knapsack :: [[Int]] -> Int -> Int
knapsack xs k = knapsackMemo xs V.! k
    where knapsackMemo :: [[Int]] -> V.Vector Int
          knapsackMemo [] = V.generate (k+1) $ \j -> if j == 0 then 0 else div maxBound 2
          knapsackMemo ([w, v]: xs) = V.modify evolve $ knapsackMemo xs
              where evolve :: MV.MVector s Int -> ST s ()
                    evolve memo = foldM_ step () [1..k]
                        where step _ j = do
                                passed <- MV.read memo j
                                selected <- MV.read memo (if j < w then 0 else j-w)
                                MV.write memo j $ min passed (selected + v)
