P5098 [USACO04OPEN] Cave Cows 3

Farmer John's $N$ ($1 \le N \le 50,000$) cows are exploring a large room in a cave. It is dark, and the cows communicate by mooing loudly at each other. Due to the strange accoustics of the room, the time it takes for a 'moo' from one cow to reach another cow is proportional to the "manhattan" distance between the two cows: that is, if cow A is at location $(X_a, Y_a)$ and cow B is at location $(X_b, Y_b)$, it takes $|X_a-X_b| + |Y_a-Y_b|$ units of time for a 'moo' from cow A to reach cow B. $X$ and $Y$ coordinates are all in the range $(-1,000,000 .. 1,000,000)$. Given the locations of the $N$ cows, determine the maximum time over all pairs of cows for a 'moo' to propagate.

* Line $1$: A single integer: $N$. * Lines $2..N+1$: Each line contains two space-separated integers, giving the $(x,y)$ coordinates of a cow.

* Line $1$: The maximum 'moo' distance among all pairs of cows

### OUTPUT DETAILS: The cows at $(2,7)$ and $(8,1)$ are separated by $|2-8| + |7-1| = 6 + 6 = 12$ units.