import Control.Monad
import qualified Data.Map as Map
import Data.List

main = do
  [hp, n] <- map read . words <$> getLine
  table <- replicateM n ((\[a, b] -> (a, b)) . map read . words <$> getLine)

  let prune m = Map.foldlWithKey' go m m where
        go m c v = Map.filterWithKey (\c' v' -> c' <= c || v <= v') m
      evolve xs = resolve $ prune $ Map.fromListWith max [(total + c, val + v) | (total, val) <- Map.toList xs, (v, c) <- table]
      resolve xs = case filter ((>=hp) . snd) $ Map.toList xs of
        (c, _) : _ -> c
        _ -> evolve xs

  print $ evolve (Map.singleton 0 0)