\(N\) con bò của Farmer John (\(1 \leq N \leq 1000\)) muốn tổ chức một hệ thống "moo-cast" khẩn cấp để truyền những thông điệp quan trọng cho nhau.

Thay vì rống gọi nhau từ xa, đàn bò quyết định tự trang bị bộ đàm, mỗi con một chiếc. Mỗi bộ đàm có bán kính truyền hữu hạn, nhưng đàn bò có thể chuyển tiếp thông điệp cho nhau theo một đường đi gồm nhiều chặng, nên không nhất thiết mọi con bò đều phải truyền trực tiếp được tới mọi con bò khác.

Đàn bò cần quyết định sẽ chi bao nhiêu tiền cho các bộ đàm. Nếu chúng chi \(X\) đô la, mỗi con sẽ nhận được một bộ đàm có khả năng truyền xa tới khoảng cách \(\sqrt{X}\). Nói cách khác, bình phương khoảng cách giữa hai con bò phải không vượt quá \(X\) để chúng có thể liên lạc.

Hãy giúp đàn bò xác định giá trị nguyên nhỏ nhất của \(X\) sao cho một thông điệp phát từ bất kỳ con bò nào cuối cùng cũng có thể tiếp cận mọi con bò khác.

Dữ liệu vào

Dòng đầu tiên chứa \(N\).

\(N\) dòng tiếp theo, mỗi dòng chứa tọa độ \(x\) và \(y\) của một con bò. Cả hai tọa độ đều là số nguyên trong khoảng \(0 \ldots 25\,000\).

Dữ liệu ra

In một dòng chứa số nguyên \(X\), là số tiền tối thiểu đàn bò phải chi cho các bộ đàm.

Ví dụ

4
1 3
5 4
7 2
6 1

17

Nguồn

USACO 2016 December Contest, Gold — Moocast. Tác giả đề: Richard Peng.

https://usaco.org/index.php?page=viewproblem2&cpid=669