7722번 - Real Fun 다국어

Yesterday it was real fun.

Today you wake up and notice that something is just not right. Not just headache, but something else is constantly annoying you. But you just can’t get what exactly. You walk around your room, enjoying the sunlight coming through the open window, through the holes in the roof. . . Stop. There were no holes in the roof until today. Definitely.

Suppressing the urge to call your friends and find out something about the origin of the holes, you decide to fix the roof first. In a modern way.

You’ve decided to nail 3 equal square boards with sides parallel to the sides of the (of course, square) roof to close all the holes, and were just wondering what is the minimal required size for these boards.

You are given N different points on a Cartesian plane and need to find minimal d such that three possibly overlapping d × d squares with sides parallel to coordinate axes can cover all the points (possibly just by the border).

The first line of the input file contains N, 4 ≤ N ≤ 200, 000. Each of the next N lines contain two integers x_i and y_i – the coordinates of i-th hole (−10⁹ ≤ x_i, y_i ≤ 10⁹). No two points coincide.

Output the minimal possible d.