Nối mạng các trạm

Có $n$ trạm phát sóng, trạm thứ $i$ đặt tại điểm nguyên $(x_i,y_i)$ trên mặt phẳng. Có thể kéo cáp nối trực tiếp hai trạm bất kỳ; cáp phải chạy dọc theo các đường lưới nên chi phí nối trạm $i$ với trạm $j$ là $|x_i-x_j|+|y_i-y_j|$.

Hãy chọn các cặp trạm để nối cáp sao cho từ mỗi trạm đều truyền được tín hiệu tới mọi trạm khác (có thể qua các trạm trung gian), với tổng chi phí nhỏ nhất. Có thể có nhiều trạm đặt tại cùng một điểm.

Dữ liệu vào

• Dòng đầu tiên chứa số nguyên $n$.
• $n$ dòng tiếp theo, dòng thứ $i$ chứa hai số nguyên $x_i,y_i$.

Dữ liệu ra

In ra tổng chi phí nhỏ nhất.

Ràng buộc

• $1\le n\le 2000$
• $0\le x_i,y_i\le {10}^9$

Ví dụ