13855번 - Three Squares 다국어

문제

There are N distinct points located at integer coordinates in the plane. We want to place three identical axis-parallel squares on the plane, such that each of the N points is located inside (or on the borders of) at least one of the squares. What is the minimum possible side length of the squares?

입력

The first line contains the integer number N (1 ≤ N ≤ 100000). The next N lines contain two space-separated integers each, the x and y coordinates of one of the points (0 ≤ x, y ≤ 10⁹ ).

출력

Print the minimum possible side length of the 3 squares, such that all the N points are covered by them.

제한

힌트

You can place the 3 squares with their bottom-left corners at the following coordinates: (0,0), (8,0), (7,1).