Cover All Points with Three Squares

Yesterday was real fun.

This morning you wake up and notice that something is just not right. It is not merely a headache; something keeps nagging at you, yet you cannot pin down exactly what it is. You pace around your room, enjoying the sunlight streaming through the open window, and through the holes in the roof... Wait. There were no holes in the roof until today. Definitely.

Suppressing the urge to call your friends and find out where the holes came from, you decide to fix the roof first, in a modern way.

You have decided to nail down 3 equal square boards, with sides parallel to the sides of your (of course, square) roof, to close all the holes, and you wonder what the minimum board size must be.

You are given $N$ distinct points on the Cartesian plane. Find the minimum $d$ such that three axis-parallel $d \times d$ squares (they may overlap) can cover all the points (a point lying on the border counts as covered).

Because all coordinates are integers, the answer $d$ is always an integer. Print $d$ as an integer.

The first line contains the number of points $N$ ($4 \le N \le 200\,000$).

Each of the next $N$ lines contains two integers $x_i$ and $y_i$, the coordinates of the $i$-th hole ($-10^9 \le x_i, y_i \le 10^9$). No two points coincide.

Print, on a single line, the minimum integer $d$ that allows all the points to be covered.