Scanf.scanf "%d %d" (fun h n ->
    let ab = Array.init n (fun _ -> Scanf.scanf " %d %d" (fun a b -> a, b)) in
    let mm = 1_000_000_000_000_000_000 in
    let l = Array.make (h + 1) mm in
    l.(h) <- 0;
    for i = h downto 1 do
        if l.(i) <> mm then (
            Array.iter (fun (a, b) ->
                let k = max 0 (i - a) in
                let bb = b + l.(i) in
                l.(k) <- min l.(k) bb) ab
        )
    done;
    Printf.printf "%d\n" l.(0)
)