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

hide comments
mahilewets: 2017-09-10 08:44:03

AC after two weeks from the day I have read the statement and submitted simple and wrong solution

mahilewets: 2017-08-30 20:10:18

Nice

Algorithm based on some Minkowski works

But WA

But WA is only my fault

mahilewets: 2017-08-26 07:28:00

Can't beat SIGSEGV

Give up

Sudarshan K: 2015-05-28 17:18:59

Nice problem :)


Added by:Minilek
Date:2008-01-10
Time limit:0.148s-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