import qualified Data.ByteString.Char8 as C
import Data.Ord
import Prelude hiding (head, tail, replicate, zipWith, (++))
import Data.Vector.Unboxed
import qualified Data.Vector.Unboxed.Mutable as UM
import Data.Vector.Algorithms.Intro

main = C.interact $ put . sol . get

get = unfoldr (C.readInt . C.dropWhile (<'0'))

put = C.pack . show

sol v = snd $ kruskal n (ex ++ ey)
  where
  n = head v
  u = tail v
  vs = generate n id
  ex = es x $ modify (sortBy (comparing x)) vs
  ey = es y $ modify (sortBy (comparing y)) vs
  x i = u!(2*i)
  y i = u!(2*i+1)
  es f is = zipWith (\i j -> (f i-f j,i,j)) (tail is) is

kruskal n = foldl' upd (newUF n, 0) . modify sort

upd (uf, a) (c,i,j) = if findUF uf i j
  then (uf, a)
  else (uniteUF uf i j, a+c)

data UnionFind = UnionFind {ids :: Vector Int, szs :: Vector Int}
 deriving Show

newUF n = UnionFind (fromList [0..n-1]) (replicate n 1)

rootUF uf p
  | p==q      = p
  | otherwise = rootUF uf q
    where
    q = (ids uf)!p

updateUF p i s uf = UnionFind
  (modify (\v -> UM.unsafeWrite v i p) (ids uf))
  (modify (\v -> UM.unsafeWrite v p s) (szs uf))

findUF uf p q = (rootUF uf p)==(rootUF uf q)

uniteUF uf p q
  | i==j      = uf
  | otherwise = if si<sj
      then updateUF j i (si+sj) uf
      else updateUF i j (si+sj) uf
  where
  (i, j) = (rootUF uf p, rootUF uf q)
  (si, sj) = ((szs uf)!i, (szs uf)!j)