let (h, n) = Scanf.sscanf (read_line ()) "%d %d" @@ fun h n -> (h, n)
let ab = Array.init n @@ fun _ -> Scanf.sscanf (read_line ()) "%d %d" @@ fun a b -> (a, b)

let () =
  let ans = Array.make (h + 1) max_int in
  ans.(0) <- 0;
  for i = 1 to h do
    Array.iter (fun (a, b) -> ans.(i) <- min ans.(i) (ans.(max 0 (i - a)) + b)) ab
  done;
  Printf.printf "%d\n" ans.(h)