60001 직각이등변삼각형 Gold V

문제

2차원 평면 위에 서로 다른 N개의 점이 있다. i번째 점의 좌표는 (x_i, y_i)이다.

직각이등변삼각형은 직각삼각형이면서 이등변삼각형인 삼각형으로, 한 내각이 직각이고 빗변이 아닌 두 변의 길이가 같다.

다음 두 조건을 모두 만족하는 직각이등변삼각형 중 빗변의 길이가 가장 짧은 것의 빗변의 길이를 구하시오.

1. N개의 점 모두가 직각이등변삼각형의 경계나 내부에 위치한다.
2. 빗변이 x축과 평행하다. (빗변의 두 끝점의 y좌표가 같다)

입력

첫째 줄에 정수 N (2 ≤ N ≤ 100,000)이 주어진다.

다음 N개의 줄에 두 정수 x_i, y_i가 주어진다. (-100,000,000 ≤ x_i, y_i ≤ 100,000,000)

출력

조건을 만족하는 직각이등변삼각형 중 빗변의 길이가 가장 짧은 것의 빗변의 길이를 출력한다. 답은 항상 정수이다.

3
0 0
2 3
4 0

6

2
0 0
5 2

7

4
1 5
3 2
6 6
7 4

10