import Data.List
import qualified Data.Vector as V

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

knapsack :: [[Int]] -> Int -> Int
knapsack xs k = knapsackMemo xs V.! k
    where knapsackMemo :: [[Int]] -> V.Vector Int
          knapsackMemo [] = V.generate (k+2) $ \j -> if j == 0 then 0 else div maxBound 2
          knapsackMemo ([w, v]: xs) =
              foldl step (knapsackMemo xs) [0..(div (k+1) w)]
                  where step memo i = V.generate (k+2) $ \j -> min (memo V.! j) ((memo V.! (if j < w then 0 else j-w)) + v)
