стандартный ввод

시간 제한2초메모리 제한1024 MB

요약

정수 격자 위의 n개 점이 한 점에서 모이는 데 필요한 최소 시간을 구한다. 각 점은 격자 방향으로 초당 한 칸씩 움직인다.

난이도: 보통10점 중 5점
유형: 기하, 이분 탐색, 수학, 구현
정답자: 아직 제출이 없습니다

문제

В стране Смешариков новый сезон! Теперь все они отправляются в поход. Для этого им нужно встретиться в одной точке, и уже оттуда отправиться покорять мир. Лосяшу, координирующему действия Смешариков, известны координаты всех участников похода. Помогите ему определить минимальное количество секунд, которое понадобится Смешарикам, чтобы собраться всем вместе.

Изначально все Смешарики находятся в узлах целочисленной сетки. Если Смешарик находится в точке $(x, y)$ , то за одну секунду он может переместиться в точки $(x, y + 1)$ , $(x + 1, y)$ , $(x - 1, y)$ или $(x, y - 1)$ , или же остаться в точке $(x, y)$ .

입력

В первой строке дано одно целое число $n$ --- количество Смешариков ( $1 \le n \le 200\\,000$ ). Далее в $n$ строках даны изначальные позиции Смешариков. Каждая позиция описывается двумя целыми числами $x\_i$ и $y\_i$ ( $-10^{18} \le x\_i, y\_i \le 10^{18}$ ).

출력

Выведите единственное число --- минимальное количество секунд, которое понадобится Смешарикам, чтобы собраться в одной точке.

예제3

예제 1
입력
```
1
1 1
```
예상 출력
```
0
```
예제 2
입력
```
2
1 3
4 4
```
예상 출력
```
2
```
예제 3
입력
```
3
0 0
3 3
0 3
```
예상 출력
```
3
```