No submission language available for this problem.

Background

Special for beginners, ^_^

Description

布鲁恩王国举办了一场盛大的热气球活动，国家里的居民纷纷搭乘自己制作的热气球飞向天空。

天空中漂浮着各种各样的热气球，美不胜收。

布鲁恩王国的国王在宫殿的观景台上看到这一幕场景感到十分地欣慰，这代表着自己对王国管理有序，人民安居乐业、生活丰富多彩。

国王想要告诉正在热气球中的人们，夜幕降临之际请大家落地，宫殿举行丰盛的宴会款待大家，菜品以巴西烤肉为主，有烤羊排、烤牛仔骨、烤肥牛、烤牛胸肉、烤肠、烤羊腿等。

现在，国王已经把这个消息告诉给了1号热气球上的人，从他开始把消息继续传递出去。假设空中的热气球用坐标 ($x$,$y$,$z$) 表示，则两个热气球 $I$, $J$ 之间传递消息所需的时间是 $min\{∣x_I −x_J∣,∣y_I−y_J​∣,∣z_I−z_J​∣\}$。

空中共有 N 个热气球，请编写程序计算，让所有热气球得到消息的最小用时总和是多少？

Format

Input

输入的第一行为一个整数 $N$，代表空中共有 $N$ 个气球。

接下来的 $N$ 行，每行三个整数 $x_i​,y_i,z_i$，表示第 $i$ 个热气球的坐标。

Output

输出为一个整数，代表最小的用时总和。

Samples

2
1 2 3
10 20 30

9

3
2 2 2
4 1 6
98 97 7

2

Limitation

对于第二组样例，1号热气球把消息传递给2号热气球，用时为1；相比于1号把消息传给3号，2号把消息传递给3号更快，用时为1。总用时为2。

对于百分百的数据，$1≤N≤10^5$，$−10^9≤x_i,y_i,z_i≤10^9$。

1s, 1024KiB for each test case.