Collusion on Two Wheels

Two bicycle courier services have competed in Metro City for many years, taking customers from each other back and forth. Recently, they have realized they would be better off attracting new customers instead. The problem is that their customers are now spread so widely across the city that some delivery times are unacceptably slow. This has led to customer dissatisfaction and a poor reputation.

The companies want to divide their current customers so that each company could run ads saying "We guarantee delivery in no more than M minutes", hoping to attract new customers. The streets of Metro City form a grid, and buildings sit at integer grid coordinates. Couriers must travel along the roads and cannot cut through buildings. Traveling one unit of distance in the x or y direction takes one minute.

Divide the current customers to minimize the longest delivery time required by either company for a courier to travel from one customer of that company to any other customer of the same company.

• A delivery is complete when the courier reaches the (x, y) address of the customer. No time is counted for walking through the customer's building.
• A courier traveling from one customer to another may pass customers of either company. Riding past a customer adds no extra delay.
• If one company ends up with only one customer, that company stations someone at the building to deliver messages there. This counts as a delivery time of zero.

The first line contains an integer N, the number of customers to divide. $2 < N \leq 1000$.

The next N lines each contain two integers x and y, the position of one customer. $0 \leq x, y \leq 1000$.

Print a single line with the longest delivery time required by the two companies, that is, the maximum of the two longest delivery times each company achieves separately.