Earliest Diffusion Time

Consider n points on the plane. Each point diffuses over time: at each unit of time, it expands its diffusion region by 1 unit in the four cardinal directions. At time t, the diffusion region for a point a=(a_x, a_y) is

[ D(a, t)={ (x,y) : |x-a_x|+|y-a_y| \le t } ]

Two points \(a\) and \(b\) are said to be connected (denoted as \(e(a,b)\)) if and only if their diffusion regions have a non-empty intersection, i.e.,

[ D(a, t)\cap D(b, t) \neq \emptyset \quad \text{which is equivalent to} \quad |a_x-b_x|+|a_y-b_y| \le 2t. ]

A connected block is defined as a set of points in which every pair of points \(u,v\) can be connected by a sequence of points:

[ e(u,a_0),; e(a_0,a_1), ; \cdots, ; e(a_k,v). ]

Given the coordinates of n points on the plane, determine the minimum integer time t such that all points form one single connected block. In other words, find the smallest integer t for which the graph, where an edge exists between points \(a\) and \(b\) if \(|a_x-b_x|+|a_y-b_y|\le 2t\), is connected.

inputFormat

The first line contains an integer n (1 ≤ n ≤ 105).

Each of the following n lines contains two integers x and y (\(|x|, |y| \leq 10⁹\)), representing the coordinates of a point.

outputFormat

Output a single integer: the minimum time t such that all points are connected. This time is given by the formula \(t = \lceil \frac{W}{2} \rceil\), where \(W\) is the maximum Manhattan distance among the edges in the minimum spanning tree of the points, with the Manhattan distance defined as \(|x_1-x_2|+|y_1-y_2|\).

sample

2
0 0
1 1

1