题目描述

三维空间中有 $\red{N}$ 个点，每个点在三维坐标$\red{(X_i,Y_i,Z_i)}$处，保证没有两个点占据同一个位置。 建造 $\red{A}$ 和 $\red{B}$ 之间的隧道所需的花费为: $\red{Cost(A,B)= min}$ { $\red{ |X_A-X_B|,|Y_A-Y_B|,|Z_A-Z_B| }$ };

现在，你需要建造一些隧道，使得这 $\red{N}$ 个点连通，即两两之间能相互到达，并且费用最小。

输入格式

输入第一行一个数 $\red{N}$，表示点的个数。

接下来 $\red{N}$ 行，每行三个数 $\red{X_i,Y_i,Z_i}$，描述每个点坐标。

输出格式

输出仅一个数，表示最小费用。

样例

输入样例

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

输出样例

4

提示

对于 $\red{ 50\% }$的数据，$\red{1<=N<=1000}$;

对于 $\red{100\%}$的数据，$\red{1<=N<=100000，|X_i|,|Y_i|,|Z_i|<=10^9}$;