VNEMPIRE - Đế chế

no tags 

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 



Added by:Trần Hải Đăng
Date:2010-05-03
Time limit:0.400s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: NODEJS OBJC PERL6 SQLITE VB.NET
Resource:COCI 2010 contest 7