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

data Action = Action !Int !Int

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 xs = resolve $ foldl' prune mempty [(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 :: Map.IntMap Int)