module PHashtbl : sig
  (* 永続ハッシュテーブル（は？） *)
  type ('a, 'b) t

  val create : ?random:bool -> int -> ('a, 'b) t
  val add : ('a, 'b) t -> 'a -> 'b -> ('a, 'b) t
  val remove : ('a, 'b) t -> 'a -> ('a, 'b) t
  val replace : ('a, 'b) t -> 'a -> 'b -> ('a, 'b) t
  val find : ('a, 'b) t -> 'a -> 'b
  val iter : ('a -> 'b -> unit) -> ('a, 'b) t -> unit
  val fold : ('a -> 'b -> 'c -> 'c) -> ('a, 'b) t -> 'c -> 'c
  val length : ('a, 'b) t -> int
end = struct
  type ('a, 'b) t = ('a, 'b) data ref
  (* 編集による差分 *)
  and ('a, 'b) data =
      Hashtbl of ('a, 'b) Hashtbl.t
    | Add of ('a, 'b) t * 'a * 'b
    | Remove of ('a, 'b) t * 'a

  let create ?(random=false) n = ref (Hashtbl (Hashtbl.create ~random n))

  (* ハッシュを使う前に，差分を解消して一番上に持ってくる *)
  let rec reroot k = function
    | { contents = Hashtbl h } -> k h
    | { contents = Add (t', i, d) } as t ->
        reroot (fun h ->
          (* 辺を逆向きに張り替える *)
          t' := Remove (t, i);
          Hashtbl.add h i d;
          k h) t'
    | { contents = Remove (t', i) } as t ->
        reroot (fun h ->
          (* 辺を逆向きに張り替える *)
          t' := Add (t, i, Hashtbl.find h i);
          Hashtbl.remove h i;
          k h) t'
  let reroot k t =
    reroot (fun h -> t := Hashtbl h; k h) t

  (* 破壊的でなかった操作は，差分を解消してからやるだけ *)
  let find t i = reroot (fun h -> Hashtbl.find h i) t
  let iter f t = reroot (Hashtbl.iter f) t
  let fold f t d = reroot (fun h -> Hashtbl.fold f h d) t
  let length t = reroot Hashtbl.length t

  (* 破壊的だった操作は，履歴を残しておく必要がある *)
  let add t i d =
    reroot (fun h ->
      let t' = ref (Hashtbl h) in
      t := Remove (t', i);
      Hashtbl.add h i d; t') t

  let remove t i =
    reroot (fun h ->
      try
        let t' = ref (Hashtbl h) in
        t := Add (t', i, Hashtbl.find h i);
        Hashtbl.remove h i; t'
      (* 要素が存在しなかった場合，何もしないので履歴を残す必要もない *)
      with Not_found -> t) t

  (* 基本操作の組み合わせで表現できるもの *)
  let replace t i d = add (remove t i) i d
end

module PUnionFind
  (Index : sig
    type t
    val compare : t -> t -> int
  end) :
sig
  (* persistent union-find data structure *)
  type t
  type class_

  val make : int -> t
  val find : t -> Index.t -> class_
  val union : t -> Index.t -> Index.t -> t

  val compare_class : class_ -> class_ -> int
end =
struct
  type t =
    { rank : (Index.t, int) PHashtbl.t;
      mutable parent : (Index.t, Index.t) PHashtbl.t }
  type class_ = Index.t

  let make n = { rank = PHashtbl.create n; parent = PHashtbl.create n }

  let rec find parent i k =
    let j = try PHashtbl.find parent i with Not_found -> i in
    if Index.compare i j = 0 then k parent i
    else find parent j (fun parent r -> k (PHashtbl.replace parent i r) r)
  let find ({ parent } as h) i =
    find parent i (fun parent r -> h.parent <- parent; r)

  let union uf x y =
    let cx = find uf x in
    let cy = find uf y in
    if Index.compare cx cy = 0 then uf
    else begin
      let rx = try PHashtbl.find uf.rank x with Not_found -> 0 in
      let ry = try PHashtbl.find uf.rank y with Not_found -> 0 in
      if rx < ry then
        { uf with parent = PHashtbl.replace uf.parent cx cy }
      else
        { parent = PHashtbl.replace uf.parent cy cx;
          rank = PHashtbl.replace uf.rank cx (rx + 1) }
    end

  let compare_class = Index.compare
end

module WeightedGraph
  (Vertex : sig
    type t
    val compare : t -> t -> int
  end)
  (Weight : sig
    type t
    val compare : t -> t -> int
  end) :
sig
  val kruskal :
    (* 頂点の数 *)
    int ->
    (* 辺のリスト *)
    (Vertex.t * Vertex.t * Weight.t) list ->
    (* 最小全域木に含まれる辺のリスト *)
    (Vertex.t * Vertex.t * Weight.t) list
end =
struct
  module UF = PUnionFind (Vertex)

  let kruskal n es =
    List.sort (fun (_, _, w) (_, _, w') -> Weight.compare w w') es
    |> List.fold_left (fun (uf, acc) (u, v, w) ->
        if UF.compare_class (UF.find uf u) (UF.find uf v) = 0
        then (uf, acc)
        else (UF.union uf u v, (u, v, w) :: acc)) (UF.make n, [])
    |> snd
end

module Int = struct
  type t = int
  let compare = compare
end

module G = WeightedGraph (Int) (Int)
 
let () =
  let n = Scanf.scanf "%d\n" @@ fun n -> n in
  let xys = Array.to_list @@ Array.init n @@ fun i ->
    Scanf.scanf "%d %d\n" @@ fun x y -> x, y, i in
  let xedges =
    List.sort (fun (x, _, _) (x', _, _) -> compare x x') xys
    |> (fun ((x, y, i) :: xys) ->
        List.fold_left (fun (acc, x, y, i) (x', y', j) ->
          ((i, j, x' - x) :: acc, x', y', j)) ([], x, y, i) xys)
    |> (fun (acc, _, _, _) -> acc) in
  let yedges =
    List.sort (fun (_, y, _) (_, y', _) -> compare y y') xys
    |> (fun ((x, y, i) :: xys) ->
        List.fold_left (fun (acc, x, y, i) (x', y', j) ->
          ((i, j, y' - y) :: acc, x', y', j)) ([], x, y, i) xys)
    |> (fun (acc, _, _, _) -> acc) in
  List.rev_append xedges yedges
    |> G.kruskal n
    |> List.map (fun (_, _, d) -> d)
    |> List.fold_left ( + ) 0
    |> Printf.printf "%d\n"

Measured memory_bytes: 43772