Non-Rotating Calipers

Vernier calipers are a type of ruler that measures dimensions such as length, height, and width of machine parts or parts of the human body with precision. The caliper has a ruler part and a jaw part, and the width is measured by placing an object between the two jaws.

In algorithm class, Jaehwi learned the rotating calipers technique used on convex hulls. When he tried to apply it as is, he realized that turning the caliper around the hull is very difficult. So he devised a simpler non-rotating calipers algorithm.

The non-rotating calipers algorithm works as follows. First, N points on a plane are given. Next, place the caliper on the same plane as the point set, with the ruler part parallel to the y-axis and the jaw part parallel to the x-axis. Then open the jaws wide enough and close them little by little until a jaw touches a point, and stop there. The caliper starts out wide open, and the distance the caliper measures is the result.

Now implement the non-rotating calipers algorithm.

The first line contains the number of points N. From the second line, the N lines each contain the coordinates x_i and y_i of a point, separated by a space. All coordinates are integers.

Print the distance measured by the caliper.

• $3 \le N \le 2413$
• $-10^9 \le x_i, y_i \le 10^9 (1\le i \le N)$

2413 is Jaehwi's student ID number.