Bus Terminal

Yongin is planning a bus route using N bus stops placed on a square grid. Choose two of the stops as central stops H1 and H2. The two central stops are connected directly, and every other stop is connected directly to exactly one of H1 and H2.

The basic distance between two grid points (x1, y1) and (x2, y2) is |x1 - x2| + |y1 - y2|. If two stops are connected to the same central stop, their route distance is the sum of their basic distances to that central stop. If they are connected to different central stops, their route distance is the distance from the first stop to its central stop, plus the distance between H1 and H2, plus the distance from the other central stop to the second stop.

Choose the two central stops and the connection for each remaining stop so that the largest route distance between any two stops is as small as possible. Compute that minimum possible value.

The first line contains an integer N (2 <= N <= 500), the number of bus stops. Each of the next N lines contains two integers x and y, the coordinates of one stop. x is the horizontal coordinate and y is the vertical coordinate. Every coordinate is a positive integer not greater than 5000, and no two stops have the same position.

Print one integer: the minimum possible value of the largest route distance between two stops.