Moving the Monkeys' Ground

Monkeys live on trees in a country represented by two-dimensional integer coordinates. The ground is a horizontal line parallel to the x-axis, and every tree is a vertical line planted at an integer x-coordinate. Each tree continues both upward and downward.

A monkey can move only up and down while on a tree. Monkeys do not jump directly from one tree to another. On the ground, they may move left or right, or climb a tree.

The distance between two monkeys is defined as follows.

1. If the two monkeys have the same x-coordinate, they are on the same tree, so their distance is the absolute difference of their y-coordinates.
2. If the two monkeys have different x-coordinates, their distance is the sum of the two vertical distances from the monkeys to the ground and the absolute difference of their x-coordinates.

King Entopia wants to move the ground to make life easier for the monkeys. The ground may only be moved to a horizontal line of the form Y = N, and it may also be left where it is. N must be an integer.

Choose the position of the ground so that the maximum distance over all pairs of monkeys is as small as possible, and output that minimum possible maximum distance.

The first line contains the number of monkeys n. n is between 2 and 50, inclusive.

The remaining input gives each monkey's coordinates x y. The absolute value of every coordinate is at most 1,000,000,000, and no two monkeys are at the same coordinate.

Output the minimum possible value of the maximum distance among all pairs of monkeys after choosing the ground position.