A courier network has n depots at integer coordinates on a city grid (two depots may share the exact same location). The travel cost between two depots is their Manhattan distance |x1 - x2| + |y1 - y2|. Report the smallest travel cost over all pairs of distinct depots (by index). If two depots coincide, that smallest cost is 0.
Input format
Line 1: an integer n, the number of depots.
Next n lines: two integers x y, the coordinates of a depot.
Output format
A single integer: the minimum Manhattan distance over all pairs.
Constraints
- 2 <= n <= 2000
- -1000000000 <= x, y <= 1000000000