\(N\) con bò của Farmer John (\(1\leq N\leq 10^5\)) sống rải rác cách xa nhau trên trang trại và muốn xây dựng một mạng liên lạc để có thể trao đổi tin nhắn điện tử dễ dàng hơn (tất nhiên, mọi tin nhắn đều chứa các biến thể của "moo").

Con bò thứ \(i\) nằm tại một vị trí phân biệt \((x_i,y_i)\), trong đó \(0\leq x_i\leq 10^6\) và \(0\leq y_i\leq 10\). Chi phí xây dựng một liên kết liên lạc giữa bò \(i\) và bò \(j\) bằng bình phương khoảng cách giữa chúng: \((x_i-x_j)^2+(y_i-y_j)^2\).

Hãy tính chi phí nhỏ nhất cần thiết để xây dựng một mạng liên lạc mà qua đó mọi con bò đều có thể liên lạc. Hai con bò có thể liên lạc nếu chúng được nối trực tiếp bởi một liên kết, hoặc nếu có một chuỗi liên kết mà tin nhắn có thể đi theo.

Lưu ý: giới hạn thời gian của bài này là 4 giây, gấp đôi mức mặc định.

Dữ liệu vào

Dòng đầu tiên chứa \(N\); mỗi dòng trong \(N\) dòng tiếp theo mô tả tọa độ nguyên \(x\) và \(y\) của một con bò.

Dữ liệu ra

In chi phí nhỏ nhất của một mạng cho phép mọi con bò liên lạc. Lưu ý rằng chi phí này có thể quá lớn để lưu trong số nguyên 32 bit và có thể cần sử dụng số nguyên 64 bit (chẳng hạn kiểu long long trong C++).

Phân nhóm

• Các test 2–3 thỏa mãn \(N\le 1000\).
• Các test 4–15 không có ràng buộc bổ sung.

Ví dụ

10
83 10
77 2
93 4
86 6
49 1
62 7
90 3
63 4
40 10
72 0

660

Nguồn

USACO 2022 February Contest, Gold — Moo Network: https://usaco.org/index.php?page=viewproblem2&cpid=1211

Tác giả: Brian Dean.