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 ≤ 10⁵).

The next N lines each contains two integers: x_i and y_i (0 ≤ x_i, y_i ≤ 10⁵).

Output

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

Example

Input:
3
0 0
0 2
2 0

Output:
2

Explanation: couriers go between junction pairs (1, 2) and (1, 3). Maximum distance is 2.