DISTANCE - Manhattan

The L1 distance of two d-dimensional points is the sum of absolute values of their coordinate differences (i.e. Σi=1d |xi - yi| for two points x,y). Given N points in the plane you must find the farthest pair of points under the L1 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 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.

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

Added by:Minilek
Date:2008-01-10
Time limit:1s-4.446s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ERL JS-RHINO NODEJS PERL6 VB.NET
Resource:MIT 1st Team Contest 2007

hide comments
2020-07-01 23:26:28
Surprised my solution was accepted immediately, very cool problem
2015-05-28 17:18:59 Sudarshan K
Nice problem :)
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.