Thành phố JOI quyết định tổ chức một cuộc triển lãm quy mô lớn.

Cuộc triển lãm lần này có hai chủ đề. Mỗi một trong \(N\) cơ sở trưng bày của thành phố sẽ tổ chức trưng bày theo đúng một trong hai chủ đề đó.

Vị trí của mỗi cơ sở được biểu diễn bằng tọa độ \((x,y)\) trên mặt phẳng. Thời gian di chuyển từ cơ sở tại \((x,y)\) đến cơ sở tại \((x',y')\) là

Với số nguyên \(a\), ký hiệu \(|a|\) biểu thị giá trị tuyệt đối của \(a\).

Để tạo sự thống nhất giữa các cơ sở cùng chủ đề và tránh gây bất tiện cho những người chỉ quan tâm đến một chủ đề, thành phố muốn phân chia chủ đề sao cho thời gian di chuyển giữa hai cơ sở cùng chủ đề ngắn nhất có thể. Có thể phân chia theo bất kỳ cách nào, miễn là không gán cùng một chủ đề cho tất cả các cơ sở.

Yêu cầu

Gọi \(M\) là thời gian di chuyển lớn nhất giữa hai cơ sở được gán cùng chủ đề. Cho vị trí của \(N\) cơ sở, hãy viết chương trình tìm giá trị nhỏ nhất có thể của \(M\).

Dữ liệu vào

Dữ liệu được cung cấp qua đầu vào chuẩn.

• Dòng đầu tiên chứa số nguyên \(N\), là số cơ sở trưng bày.
• Dòng thứ \(i+1\) (\(1\le i\le N\)) chứa hai số nguyên \(x_i,y_i\), cách nhau bởi dấu cách, cho biết cơ sở thứ \(i\) nằm tại tọa độ \((x_i,y_i)\).

Không có hai cơ sở nào nằm tại cùng một tọa độ.

Dữ liệu ra

In ra đầu ra chuẩn đúng một dòng chứa giá trị nhỏ nhất có thể của \(M\), tức thời gian di chuyển lớn nhất giữa hai cơ sở cùng chủ đề.

Ràng buộc

• Giới hạn trong kỳ thi gốc: thời gian \(1\) giây, bộ nhớ \(64\) MB.
• \(3\le N\le100000=10^5\).
• \(|x_i|\le100000=10^5\) và \(|y_i|\le100000=10^5\) (\(1\le i\le N\)).
• Các tọa độ \((x_i,y_i)\) đôi một khác nhau.
• Mọi giá trị trong dữ liệu vào đều là số nguyên.

Phân nhóm

Bài này có tổng cộng \(20\) điểm, gồm \(10\) bộ dữ liệu, mỗi bộ \(2\) điểm. Các tỷ lệ dưới đây được tính trên tổng điểm của bài.

• \(40\%\) số điểm dành cho các dữ liệu thỏa mãn \(N\le2000\).

Ví dụ

5
0 0
1 0
-1 -2
0 1
-1 1

3