Problem Description

John’s $N$ ($1 \leq N \leq 50000$) cows are exploring in a pitch-black cave, and they can only communicate by calling.

The time for sound to travel is determined by the Manhattan distance between two cows. That is, for cow 1 and cow 2 to communicate, the required time is $|x_1-x_2|+|y_1-y_2|$. Here, $-10^6 \leq x_1,x_2,y_1,y_2 \leq 10^6$.

What is the maximum communication time among all pairs of cows?

Input Format

The first line contains $N$. Each of the following lines contains the coordinates of one cow.

Output Format

The maximum communication time (i.e., the maximum Manhattan distance).

5
1 1
3 5
2 7
8 1
4 4

12

Hint

Explanation of the sample:

The distance between $(2,7)$ and $(8,1)$ is the largest, which is $12$.

Translated by ChatGPT 5