{-# LANGUAGE BangPatterns #-}
import Control.Monad
import qualified Data.IntMap.Strict as Map
import Data.List
import Debug.Trace

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

  let prune m (c, v) = case Map.lookupLE c m of
        Just (_, v') | v <= v' -> m
        _ -> Map.insert c v m
      
      evolve 0 xs = xs
      evolve iter xs = evolve (iter - 1) $ foldl' prune mempty
          $ [(total + c, val + v) | (total, val) <- Map.toList xs, (v, c) <- (total, val) : table]
      resolve xs = case filter ((>=hp) .snd) $ Map.toList xs of
        (c, _) : _ -> c

  print $ resolve $ evolve 14 (Map.singleton 0 0 :: Map.IntMap Int)