Scanf.scanf "%d" (fun k ->
    let digits a =
        let rec loop i acc =
            if i = 0 then acc else loop (i / 10) ((i mod 10) :: acc)
        in
        loop a []
    in
    let count r =
        let rec loop prev edge inner = function
            | [] -> Array.fold_left (+) 0 inner + if edge then 1 else 0
            | hd :: tl -> (
                let newinner = Array.make 10 0 in
                for i = 0 to 9 do
                    if i > 0 then newinner.(i - 1) <- newinner.(i - 1) + inner.(i);
                    if i < 9 then newinner.(i + 1) <- newinner.(i + 1) + inner.(i);
                    newinner.(i) <- newinner.(i) + inner.(i);
                    if i > 0 then newinner.(i) <- newinner.(i) + 1;
                done;
                if edge && prev > 0 && prev - 1 < hd then newinner.(prev - 1) <- newinner.(prev - 1) + 1;
                if edge &&             prev     < hd then newinner.(prev)     <- newinner.(prev)     + 1;
                if edge && prev < 9 && prev + 1 < hd then newinner.(prev + 1) <- newinner.(prev + 1) + 1;
                let edge = edge && abs (hd - prev) <= 1 in
                loop hd edge newinner tl
            )
        in
        match digits r with
        | [] -> 0
        | hd :: tl -> (
            let inner = Array.make 10 0 in
            for i = 1 to hd - 1 do
                inner.(i) <- 1;
            done;
            loop hd true inner tl
        )
    in
    let rec bin left right =
        if left = right then left else
            let m = (left + right) / 2 in
            if count m < k then bin (m + 1) right
                           else bin left m
    in
    bin 1 3234566668 |> Printf.printf "%d\n"
)