Page not loading? Try clicking here.
Placeholder

#2246

터널 1s - MB

Problems

3차원 좌표계에 N개의 행성이 있으며, i번 행성은 (x_i,y_i,z_i) 좌표에 위치해있다. 여기에 N-1개의 터널을 건설하여 행성들을 모두 연결하고자 하는데, 임의의 i번 행성과 j번 행성에 터널을 지을 경우의 비용은 다음과 같다.

COST[i,j] = min\{ |x_i-x_j| , |y_i-y_j|, |z_i-z_j| \}

터널이 지어졌을 때 비용의 합을 최소화 하는 프로그램을 작성하라.


Input

입력의 첫번째 줄에는 행성의 개수 N ( 1 <= N <= 1,000 )이 입력된다.

그 다음 N개의 줄에는 행성들의 x, y, z 좌표가 입력되며, 이는 -10^9 이상 10^9 이하의 정수이다. 동일 좌표에 여러개의 행성이 있는 경우는 존재하지 않는다.


Output

첫번째 줄에 비용의 합의 최소값을 출력한다.


Example #1

2

1 5 10

7 8 2
3

Example #2

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

Example #3

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


Source

COCI 2009/2010 contest7 4 (변형)

You must sign in to write code.