## MCOMP - Manhattan Companies

no tags

Everyone knows what Manhattan streets look like. For simplicity, we'll say there are two types of streets: horizontal and vertical (when seen on a map). For two junctions A and B, with coordinates (ax, ay), (bx, by) respectively, we define distance( A, B ) = |ax-bx| + |ay-by|.

A company in Manhattan has the following problem: we have to link N junctions by couriers in such a way that each pair of  junctions can communicate through the couriers. We must use the minimal possible number of couriers to do so. Also, of all the possible solutions with the minimal number of couriers, we'll take the one that minimizes the maximum distance of assigned junction pairs over all the couriers.

### Input

The first line of input contains a single integer: N (2 <= N <= 105).
The next N lines each contains two integers: xi and yi (0 <= xi, yi <= 105).

### Output

The first and only line of output should contain the minimal maximum distance over all the couriers defined above.

### Example

```Input:
30 00 22 0Output:
2```
`Explanation: couriers go between junction pairs ( 1, 2 ) and ( 1, 3 ). Maximum distance is 2.`

 Added by: gustav Date: 2010-09-23 Time limit: 0.116s-2s Source limit: 50000B Memory limit: 1536MB Cluster: Cube (Intel G860) Languages: All except: ASM64 Resource: own problem