#832 Dadasquare

Statement

Statement language

There are $N$ points on a plane. The coordinates of the $i$ -th point are $(x_i,y_i)$ .

Dadas wants to cover all the points with exactly four squares of equal size.

The sides of each square must be parallel to the coordinate axes. The squares may overlap. A point is considered covered if it lies inside or on the boundary of at least one square.

Let $L$ be the common side length of the four squares. Find the minimum possible $L$ such that every point is covered by at least one square.

Input

The first line contains the number of points, $N$ .

Each of the next $N$ lines contains two integers $x_i,y_i$ , the coordinates of the -th point.

Output

Print the minimum side length of four equal-sized squares that together cover all the points.

Constraints

$1 \le N \le 200\,000$ .
$-10^9 \le x_i,y_i \le 10^9$ ().

Subtasks

#	Score	Constraints
1	20	$N \leq 10$ .
2	30	$N \leq 5000$ .
3	50	No additional constraints.

Samples

Sample 1

Input

Output

3

Sample 2

Input

Output

2

Sample 3

Input

Output

0