Planet Tunnels

Time limit1sMemory limit128 MB

Summary
Given N 3D points with edge cost equal to the minimum coordinate-axis distance between two points, find the minimum spanning tree cost connecting all of them efficiently.
Level

Hard8 of 10

Topics
Minimum spanning tree, Sorting, Union-find
Solved
No attempts yet

Problem

In the year 2040, Minhyeok builds his own kingdom in space consisting of NN planets. To rule them efficiently he wants to build tunnels connecting the planets.

Each planet is a point in 3D space. The cost of a tunnel between planets A(xA,yA,zA)A(x_A, y_A, z_A) and B(xB,yB,zB)B(x_B, y_B, z_B) is min⁡(∣xA−xB∣, ∣yA−yB∣, ∣zA−zB∣)\min(|x_A - x_B|,\ |y_A - y_B|,\ |z_A - z_B|).

Minhyeok wants to build exactly N−1N-1 tunnels so that all planets are connected. Write a program that computes the minimum total cost to connect all planets with tunnels.

Input

The first line contains the number of planets NN (1≤N≤100 0001 \le N \le 100\,000). Each of the next NN lines contains the xx, yy, and zz coordinates of a planet. Each coordinate is an integer between −109-10^9 and 10910^9. No two planets share the same position.

Output

Print the minimum total cost to connect all planets with tunnels.

Examples1

  1. Example 1

    Input
    5
11 -15 -15
14 -5 -15
-1 -1 -5
10 -4 -1
19 -4 19
    Expected output
    4