module WeightedGraph
  (* 辺の重み *)
  (Weight : sig
    type t
    val zero : t
    val ( + ) : t -> t -> t
    val compare : t -> t -> int
  end)
  (* 辺の重みを優先度としたヒープの実装 *)
  (Heap : sig
    type t
    type elt (* 頂点に相当 *)
    type key = Weight.t (* 辺の重みに相当 *)
    (* ヒープが空ならNoneを，
       そうでなければ重みが最小となるbindingを一つ返す
       返したbindingはヒープから削除される *)
    val take_min_binding : t -> (key * elt) option
    (* ヒープにbindingを追加する
       既に同じ頂点についてのbindingが追加されていたら，
       重みが小さい方だけを残しても良いし，何も考えずに追加してもよい．
       前者の実装ならプリム法の実装が時間計算量O((V + E) log V)，
       空間計算量O(V)に改善する *)
    val add : t -> key -> elt -> unit
  end)
  (* 頂点を添字，辺の重みを要素とした配列の実装 *)
  (Array : sig
    type t
    type key = Heap.elt
    type elt = Heap.key
    val get : t -> key -> elt
    val set : t -> key -> elt -> unit
  end)
: sig
  type weight = Array.elt
  type vertex = Array.key

  (* プリム法で最小全域木を求める *)
  val minimum_spanning_tree :
    (* 空なヒープ *)
    Heap.t ->
    (* 全ての頂点について無限大で初期化された配列 *)
    Array.t ->
    (* 最小全域木を求めたいグラフの，ある頂点から伸びる辺に対してのイテレータ *)
    (vertex -> (vertex -> weight -> unit) -> unit) ->
    (* 頂点の一つ（これは必ず最小全域木に含まれる） *)
    vertex ->
    (* 最小全域木に含まれる辺の重みの総和 *)
    weight
end
= struct
  type weight = Array.elt
  type vertex = Array.key

  let minimum_spanning_tree q d es s =
    Heap.add q Weight.zero s;
    let rec prim acc u =
      Array.set d u Weight.zero;
      es u (fun v w ->
        if 0 < Weight.compare (Array.get d v) w then
          (Array.set d v w; Heap.add q w v));
      prim' acc
    and prim' acc =
      match Heap.take_min_binding q with
      | None -> acc
      | Some (w, u) ->
          if 0 < Weight.compare w (Array.get d u)
          then prim' acc
          else prim (Weight.( + ) acc w) u in
    prim Weight.zero s
end

module Int = struct
  type t = int
  let zero = 0
  let ( + ) = ( + )
  let compare = compare
end

module IntMap = Map.Make (Int)

module G = WeightedGraph (Int)
  (struct
    type t = int list IntMap.t ref
    type key = int
    type elt = int
    let take_min_binding q =
      match IntMap.min_binding !q with
      | exception Not_found -> None
      | (w, [v]) -> q := IntMap.remove w !q; Some (w, v)
      | (w, v :: vs) -> q := IntMap.add w vs !q; Some (w, v)
    let add q w v =
      q := IntMap.add w (v :: try IntMap.find w !q with Not_found -> []) !q
  end)
  (struct
    type t = int array
    type key = int
    type elt = int
    let get = Array.get
    let set = Array.set
  end)

let () = Scanf.scanf "%d\n" @@ fun n ->
  let xys = Array.to_list @@ Array.init n (fun i -> Scanf.scanf "%d %d\n" (fun x y -> x, y, i)) in
  let es = Array.make n [] in
  begin match List.sort (fun (x, _, _) (x', _, _) -> compare x x') xys with
  | [] -> ()
  | (x, y, i) :: rest ->
      ignore @@ List.fold_left (fun (x, y, i) (x', y', j) ->
        es.(i) <- (j, min (abs (x - x')) (abs (y - y'))) :: es.(i);
        es.(j) <- (i, min (abs (x - x')) (abs (y - y'))) :: es.(j);
        (x', y', j)) (x, y, i) rest
  end;
  begin match List.sort (fun (_, y, _) (_, y', _) -> compare y y') xys with
  | [] -> ()
  | (x, y, i) :: rest ->
      ignore @@ List.fold_left (fun (x, y, i) (x', y', j) ->
        es.(i) <- (j, min (abs (x - x')) (abs (y - y'))) :: es.(i);
        es.(j) <- (i, min (abs (x - x')) (abs (y - y'))) :: es.(j);
        (x', y', j)) (x, y, i) rest
  end;
  Printf.printf "%d\n" @@
  G.minimum_spanning_tree (ref IntMap.empty) (Array.make n max_int)
    (fun i f -> List.iter (fun (j, w) -> f j w) es.(i)) 0


Measured memory_bytes: 41980