SP2320 DISTANCE - Manhattan

The $L_{1}$ distance of two d-dimensional points is the sum of absolute values of their coordinate differences (i.e. $\sum_{i=1}^{d} |x _{i}-y_{i}|$ for two points $x,y$). Given $N$ points in the plane you must find the farthest pair of points under the $L _{1}$ distance metric and output their distance.

The first line of the input is `N d` ($2 \le N \le 100000, 1 \le d \le 6$) signifying that there are N points in d-dimensional space. N lines then follow, where the ith line is a space-separated list of d numbers, the coordinates of the ith point. All given coordinates are integers that are at most $1000000$ in absolute value, and all given points are distinct.

Your output should consist of a single integer, the farthest distance between a pair of input points, followed by a newline.