Đế chế

Xem PDF
Tất cả bài nộp
Các bài nộp tốt nhất
Tác giả:
tkluannguyendang
Dạng bài
Điểm: 350 (p) Thời gian: 1.0s Bộ nhớ: 512M Input: bàn phím Output: màn hình

Một đế chế đang xây dựng mạng lưới cho các hành tinh trong nó. Đế chế gồm có \(N\) hành tinh được biểu diễn như các điểm trong không gian 3 chiều. Chi phí phải chi cho việc nối giữa hành tinh \(A\) và hành tinh \(B\) là \(min\){ |\(x_A - x_B\)|, |\(y_A - y_B\)|, |\(z_A\) - \(z_B\)| } với (\(x_A\), \(y_A\), \(z_A\)), (\(x_B\), \(y_B\), \(z_B\)) là tọa độ của hành tinh \(A\), \(B\) trong không gian 3 chiều.

Đế chế dự tính sẽ xây dựng \(N – 1\) cầu nối như vậy để các hành tinh liên thông với nhau và chi phí để trả sao cho phải nhỏ nhất có thể.

Input

  • Dòng đầu là số hành tinh \(N\).
  • N dòng sau mỗi dòng là tọa độ của một hành tinh.

Output

  • Ghi trên một dòng duy nhất chi phí nhỏ nhất có thể.

Example

Test 1

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

Bình luận