정사각형 세 개

평면 위에 서로 다른 점 $N$개가 있고, 각 점의 좌표는 정수다. 축에 평행하고 한 변의 길이가 같은 정사각형 3개를 놓아서 $N$개의 점이 모두 어느 한 정사각형의 내부 또는 경계에 놓이게 하려고 한다. 이때 한 변의 길이의 최솟값을 구하시오.

정사각형은 평면 어디에나 놓을 수 있고, 서로 겹쳐도 된다.

첫째 줄에 점의 개수 $N$이 주어진다 ($1 \le N \le 100\,000$).

다음 $N$개의 줄에는 각 점의 $x$좌표와 $y$좌표가 공백으로 구분되어 하나씩 주어진다 ($0 \le x, y \le 10^9$). 모든 점은 서로 다르다.

$N$개의 점을 모두 덮는 정사각형 3개의 한 변의 길이 중 최솟값을 한 줄에 출력한다. 이 값은 항상 정수다.

첫 번째 예제에서는 한 변의 길이가 2인 정사각형 3개를 왼쪽 아래 꼭짓점이 각각 $(0, 0)$, $(8, 0)$, $(7, 1)$이 되도록 놓으면 다섯 점이 모두 덮인다.