DISTANCE  Manhattan
The L_{1} distance of two ddimensional points is the sum of absolute values of their coordinate differences (i.e. Σ_{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.
Input
The first line of the input is "N d" (2 ≤ N ≤ 100000, 1 ≤ d ≤ 6) signifying that there are N points in ddimensional space. N lines then follow, where the ith line is a spaceseparated 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.
Output
Your output should consist of a single integer, the farthest distance between a pair of input points, followed by a newline.
Example
Input: 3 2 0 0 5 0 1 1 Output: 7
hide comments
toemmsche:
20200701 23:26:28
Surprised my solution was accepted immediately, very cool problem 

Sudarshan K:
20150528 17:18:59
Nice problem :) 
Added by:  Minilek 
Date:  20080110 
Time limit:  1s4.446s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ERL JSRHINO NODEJS PERL6 VB.NET 
Resource:  MIT 1st Team Contest 2007 