Description

Given $n$ points in a $d$-dimensional space, find the maximum Manhattan distance between any two points.

For two $d$-dimensional points $(x_1,x_2,\ldots,x_d)$ and $(y_1,y_2,\ldots,y_d)$, their Manhattan distance is defined as $|x_1-y_1|+|x_2-y_2|+\ldots+|x_d-y_d|$.

Input Format

The first line contains two integers $n$ and $d$.

The next $n$ lines each contain $d$ integers describing the coordinates of a point.

Output Format

Output the maximum Manhattan distance.

4 2
2 1
1 4
4 5
5 3

6

Hint

Constraints

• For $60\%$ of the testdata, it is guaranteed that $d \le 2$.
• For $100\%$ of the testdata, it is guaranteed that $2 \le n \le 10^6$, $d \le 4$, and each coordinate satisfies $1 \le x_i \le 10^5$.

Translated by ChatGPT 5