Giải bài trực tuyến

An empire is building a network for its own planets. The empire consists of N planets, represented as points in the 3D space. The cost of connecting planet A and planet B is min{ |xA - xB|, |yA - yB|, |zA - zB| } with (xA, yA, zA), (xB, yB, zB) are coordinates of planet A, B in space. The empire is planning to build N - 1 connection and the requirement is that all planets are connected with each other and the cost is minimized.

Input

• Number of planets N (N < 100001).
• Next N lines, one line represents one coordiate of a planet.

Output

Only the minimum cost.

Example

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

Output 
4