P1648 Guard

Given $n$ points in a $d$-dimensional space, find the maximum Manhattan distance between any two points. For two $d$-dimensional points $(x_1,x_2,\ldots,x_d)$ and $(y_1,y_2,\ldots,y_d)$, their Manhattan distance is defined as $|x_1-y_1|+|x_2-y_2|+\ldots+|x_d-y_d|$.

The first line contains two integers $n$ and $d$. The next $n$ lines each contain $d$ integers describing the coordinates of a point.

Output the maximum Manhattan distance.

Constraints - For $60\%$ of the testdata, it is guaranteed that $d \le 2$. - For $100\%$ of the testdata, it is guaranteed that $2 \le n \le 10^6$, $d \le 4$, and each coordinate satisfies $1 \le x_i \le 10^5$. Translated by ChatGPT 5