配点 : 400 点
問題文
M 在维度空间中 N 点 1,2,...,N 和点 i 的坐标是 (A_{i,1}, A_{i,2}, ... , A_{i,M}) 。
与这些不同 2 当您选择一个点时 2 找到点之间的最大曼哈顿距离。
这里,有 2 点 (P_1, P_2, ... , P_M) 和 按字典顺序比较 (Q_1, Q_2, ... , Q_M) 的曼哈顿距离是 |P_i - Q_i| (1 \leq i \leq M)。
制約
- 2 \leq N \leq 2 \times 10^5
- 1 \leq M \leq 2 \times 10^5
- 2 \leq N \times M \leq 2 \times 10^5
- -10^9 \leq A_{i,j} \leq 10^9 (1 \leq i \leq N, 1 \leq j \leq M)
- 所有输入均为整数
入力
输入是按以下格式从标准输入给出的。
N M
A_{1,1} A_{1,2} ... A_{1,M}
A_{2,1} A_{2,2} ... A_{2,M}
\vdots
A_{N,1} A_{N,2} ... A_{N,M}
出力
打印答案。 来自
入力例 1
4 3 2 3 2 2 1 6 1 4 7 0 0 5
出力例 1
8
下面将曼哈顿距离简称为距离。 这时,
- 点 1 和点 2 的距离是 给出 |2 - 2| + |3 - 1| + |2 - 6| = 6
- 点 1 和点 3 的距离是 给出 |2 - 1| + |3 - 4| + |2 - 7| = 7
- 点 1 和点 4 的距离是 给出 |2 - 0| + |3 - 0| + |2 - 5| = 8
- 点 2 和点 3 的距离是 给出 |2 - 1| + |1 - 4| + |6 - 7| = 5
- 点 2 和点 4 的距离是 给出 |2 - 0| + |1 - 0| + |6 - 5| = 4
- 点 3 和点 4 的距离是 给出 |1 - 0| + |4 - 0| + |7 - 5| = 7
,所以两点之间的距离最大值为 1 和点 4 的距离 8 。
入力例 2
10 4 0 0 0 2 0 0 0 4 0 0 0 8 0 0 1 6 0 0 3 2 0 0 6 4 0 1 2 8 0 2 5 6 0 5 1 2 1 0 2 4
出力例 2
12
空间的维数为 4 可能不止这些。