let () = Scanf.scanf "%d %d\n" @@ fun h n ->
  let abs = Array.init n @@ fun _ -> Scanf.scanf "%d %d\n" @@ fun a b -> a, b in
  let dp = Array.make (h + 10001) 1145141919810 in
  dp.(0) <- 0;
  Array.iter (fun (a, b) ->
    for i = a downto 0 do
      dp.(i) <- min b dp.(i)
    done) abs;
  for i = 0 to h do
    Array.iter (fun (a, b) ->
      dp.(i + a) <- min dp.(i + a) (dp.(i) + b)) abs
  done;
  Printf.printf "%d\n" @@ dp.(h)
