Goal
Casablanca’s hippodrome has grown tired of old-fashioned dual racing and has kicked it up a notch: they will now be organizing hyperduals.
During a hyperdual, only two horses will participate in the race. In order for the race to be interesting, it is necessary to try to select two horses with similar strength.
Write a program which, using a given number of strengths, identifies the two closest strengths and shows their difference with an integer.
In a hyperdual, a horse's strength is a bidimensional (Velocity,Elegance) vector. The distance between two strengths (V1,E1) and (V2,E2) is abs(V2-V1)+abs(E2-E1).
(This is a harder version of training puzzle “Horse-racing duals”. You may want to solve that problem first.)
(To date there is no specific achievement if you solve this one in pure bash. Rest assured it *is* possible nonetheless!)
Input
Line 1: the number N of horses
N following lines: the speed Vi and elegance Ei of each horse, space-separated
Output
Line 1: the distance D between the two closest strengths
Constraints
10 ≤ N ≤ 600
0 ≤ Vi,Ei ≤ 10000000
D ≥ 0
All values are integral.
Example
Input
10
6850207 0
8707138 0
8028585 0
3635318 0
8612162 0
6854699 0
7106093 0
3721952 0
2670046 0
1746583 0
