MIT 1st Team Contest 2007

The L₁ distance of two d-dimensional 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₁ 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