P5098 [USACO04OPEN] Cave Cows 3

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?

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

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

Explanation of the sample: The distance between $(2,7)$ and $(8,1)$ is the largest, which is $12$. Translated by ChatGPT 5