[요약] N 개의 위성으로 이루어져 우주에 N-1 개의 터널을 만들어 연결시키려 한다.

위성은 3 차원 점으로 표시된다. A 위성에서 B 위성으로 가는 터널의 비용은 다음과 같다.

A 에서 B 로의 터널을 두는데의 비용은 아래와 같다.

TunnelCost[A,B] = min{ |xA-xB|, |yA-yB|, |zA-zB| }

위성 A 의 점은 xA, yA, zA 이다. 위성 B 의 점은 xB, yB, zB 이다.

이 프로젝트를 마치기 위한 최소의 비용을 출력하시오.

TunnelCost[A,B] = min{ |xA-xB|, |yA-yB|, |zA-zB| }

where (xA, yA, zA) are 3D coordinates of planet A, and (xB, yB, zB) are coordinates of planet B. The Empire needs to build exactly N - 1 tunnels in order to fully connect all planets, either by direct links or by chain of links. You need to come up with the lowest possible cost of successfully completing this project.

입력

• The first line of input contains one integer N (1 ≤ N ≤ 100 000), number of planets.
• Next N lines contain exactly 3 integers each. All integers are between -10^9 and 10^9 inclusive. Each line contains the x, y, and z coordinate of one planet (in order).

No two planets will occupy the exact same point in space.

출력

입출력 예

입력

2
1 5 10
7 8 2

출력

3

입력

3
-1 -1 -1
5 5 5
10 10 10

출력

11

입력

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

출력

4

출처:coci