두 집 사이의 거리 1000초 64MB

문제

N개의 집이 2D 평면상에 주어졌을때, 각 집은 (x_i, y_i)라는 좌표로 위치가 주어진다. 각 집은 서로 다른 위치에 있으며, 두 집 a와 b 사이의 거리는 |x_a - x_b| + |y_a - y_b|의 수식으로 계산된다.

가장 멀리 떨어진 두 집의 거리를 구하는 프로그램을 작성하시오.

첫째 줄에 정수 N이 주어진다. (2 \le N \le 500,000)

다음 N개의 줄에는 각 점의 x, y좌표가 주어진다. 각 좌표의 범위는 -10^9 이상 10^9이하이다.

첫 줄에 가장 멀리 떨어진 두 집의 거리를 출력한다.

번호	점수	조건
#1	30점	N \le 3000
#2	70점	추가 제약 조건 없음

입력

5keyboard_return
1space_bar4keyboard_return
3space_bar1keyboard_return
6space_bar2keyboard_return
7space_bar5keyboard_return
4space_bar7

출력

USACO US Open 2004 Orange 3번