iPig has just finished a boring Pig-Language class at the Fat Pig School. Being naturally gifted, iPig found the class incredibly simple and felt very lonely. To alleviate his loneliness, he decided to play a game with his good friend giPi (Chicken Skin)—hide and seek.

However, they felt that playing regular hide and seek was not interesting enough and not "lonely" enough. So, they decided to play the extremely lonely "Crab-style" hide and seek. As the name suggests, they can only move horizontally or vertically while playing. After a lonely round of rock-paper-scissors, they decided that iPig would seek giPi. Since they are both very familiar with the terrain of the Fat Pig School, giPi will only hide in one of $N$ secret locations, and obviously, iPig will only search for giPi among those $N$ locations.

At the start of the game, they choose one location from these $N$ secret locations. iPig stays put, and giPi takes 30 seconds to flee the scene (obviously, giPi will not stay at the starting location). Then, iPig randomly searches for giPi until he finds him. Because iPig is lazy, he always takes the shortest path. Furthermore, he does not choose his starting point randomly; he wants to find a location such that the difference between the distance to the farthest location (excluding the starting location itself) and the distance to the nearest location (excluding the starting location itself) is minimized.

iPig now wants to know what this minimum distance difference is.

Since iPig does not have a computer on hand, he cannot program a solution to this simple problem, so he immediately called you to help him solve it. iPig has provided you with the coordinates of the $N$ secret locations at the Fat Pig School. Please write a program to solve iPig's problem.

Input

Line 1: An integer $N$. Lines 2 to $(N + 1)$: Each line contains two integers $X_i, Y_i$, representing the coordinates of the $i$-th location.

Output

A single integer representing the minimum distance difference.

Examples

Input 1

4
0 0
1 0
0 1
1 1

Output 1

1

Constraints

For 30% of the data, $2 \le N \le 1000$. For 100% of the data, $2 \le N \le 100000$, $0 \le X_i, Y_i \le 100000000$. The data guarantees there are no duplicate points.