let h, dp, ab_s = Scanf.(scanf "%d %d" @@ fun h n -> Array.(h, make (h + 1) (1 lsl 40), init n @@ fun _ -> scanf " %d %d" @@ fun a b -> a, b))
let _ = for i = 1 to h do Array.iter (fun (a, b) -> dp.(i) <- min dp.(i) @@ if a >= i then b else dp.(i - a) + b) ab_s done; Printf.printf "%d\n" @@ dp.(h)