Thành phố Yong-In dự định xây dựng một mạng xe buýt với \(N\) bến, mỗi bến nằm ở một góc phố. Yong-In là một thành phố hiện đại, có bản đồ dạng lưới gồm các khu phố hình vuông bằng nhau. Khoảng cách giữa hai bến là độ dài đường đi ngắn nhất dọc theo các con đường. Do đó, khoảng cách giữa hai bến có tọa độ \((x_1,y_1)\) và \((x_2,y_2)\) được tính bằng \(|x_1-x_2|+|y_1-y_2|\).

Thành phố muốn thiết lập mạng tuyến xe như sau:

• Chọn hai bến khác nhau làm hai bến trung tâm \(H_1,H_2\) và nối trực tiếp chúng với nhau.
• Nối mỗi bến còn lại với đúng một trong hai bến trung tâm.
• Không có tuyến nối trực tiếp nào khác.

Độ dài mỗi tuyến nối trực tiếp bằng khoảng cách giữa hai đầu mút. Để đi giữa hai bến, hành khách sử dụng đường đi duy nhất trong mạng đã thiết lập; độ dài hành trình là tổng độ dài các tuyến trên đường đi đó.

Nếu hai bến \(A,B\) cùng nối với bến trung tâm \(H_1\), hành trình đi từ \(A\) qua \(H_1\) đến \(B\). Nếu \(A\) nối với \(H_1\) còn \(B\) nối với \(H_2\), hành trình đi từ \(A\) qua \(H_1\), rồi \(H_2\) và cuối cùng đến \(B\).

Nhà chức trách Yong-In muốn mọi người dân có thể đến mọi nơi trong thành phố nhanh nhất có thể. Vì vậy, họ muốn chọn hai bến trung tâm và cách nối các bến sao cho hành trình dài nhất giữa hai bến bất kỳ ngắn nhất có thể.

Với mỗi cách chọn hai bến trung tâm và phân các bến còn lại cho chúng, xét hành trình dài nhất giữa một cặp bến bất kỳ. Hãy tìm giá trị nhỏ nhất có thể của độ dài hành trình dài nhất này.

Dữ liệu vào

• Dòng đầu chứa \(N\), với \(2\le N\le 500\).
• Mỗi dòng trong \(N\) dòng tiếp theo chứa hai số nguyên \(x,y\) là tọa độ của một bến, với \(1\le x,y\le 5000\).
• Không có hai bến nào cùng vị trí.

Dữ liệu ra

In một số nguyên dương: giá trị nhỏ nhất của độ dài hành trình dài nhất.

Chấm điểm

Có 20 bộ kiểm tra, mỗi bộ tương ứng 5 điểm trong thang điểm gốc 100. Một bộ kiểm tra chỉ được điểm khi kết quả đúng và chương trình chạy trong giới hạn thời gian; ngược lại được 0 điểm.

Ví dụ

6
1 7
16 6
12 4
4 4
1 1
11 1

20

7
7 9
10 9
5 3
1 1
7 2
15 6
17 7

25

Nguồn

Đề gốc IOI 2002. Tài liệu kỳ thi.