309. Real Fun

Time limit per test: 0.75 second(s)
Memory limit: 65536 kilobytes
input: standard
output: standard



Yesterday it was real fun.

Today you wake up and notice that something is just not right. Not just headache, but something else is constantly annoying you. But you just can't get what exactly. You walk around your room, enjoying the sunlight coming through the open window, through the holes in the roof... Stop. There were no holes in the roof until today. Definitely.

Suppressing the urge to call your friends and find out something about the origin of the holes, you decide to fix the roof first. In a modern way.

You've decided to nail 3 equal square boards with sides parrallel to the sides of the (of course, square) roof to close all the holes, and were just wondering what is the minimal required size for these boards.

Formally speaking, you are given n different points on a Cartesian plane and need to find minimal d such that three possibly overlapping d x d squares with sides parallel to coordinate axes can cover all the points (possibly just by the border).

Input
The first line of the input file contains n (4 ≤ n ≤ 20000).

The next n lines contain two integer numbers each, x and y — the coordinates of the holes (-109 ≤ x, y ≤ 109). No two points coincide.

Output
Output the minimal possible d.

Example(s)
sample input
 
sample output
 
4
0 1
0 -1
1 0
-1 0

1


sample input
 
sample output
 
12
0 1
0 -1
1 0
-1 0
10 1
10 -1
11 0
9 0
20 1
20 -1
21 0
19 0

2