Map Labels

You want to place city names on a map without overlaps.

The position of each city is given as an (x, y) coordinate. Every city name is written inside an axis-aligned rectangle of the same size, and each rectangle's width is three times its height. For a city, the rectangle is placed to the lower right of the city coordinate, using the city coordinate as its upper-left corner. For instance, if the city is at (5, 3) and the rectangle has width 3 and height 1, the rectangle occupies the region from (5, 3) to (8, 2).

Two rectangles may share points or line segments on their boundaries. They must not overlap in any region with positive area.

Find the maximum possible height of the rectangles so that every city can be labeled. The width of each rectangle is always three times that value.

The first line contains the number of cities n. (2 ≤ n ≤ 100,000)

Each of the next n lines contains two nonnegative integers x and y, the coordinates of one city. (0 ≤ x, y ≤ 1,000,000)

No two cities are given with the same coordinates.

Print the maximum possible rectangle height on the first line.

Round the answer to the second digit after the decimal point, and always print exactly two digits after the decimal point.