AT_pakencamp_2025_day1_i Dist Max

$ 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 $ ) の和となります。

入力は以下の形式で標準入力から与えられる。 > $ 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} $

答えを出力せよ。

### Sample Explanation 1 以下、マンハッタン距離のことを単に距離と表記します。 このとき、 - 点 $ 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 $ です。 ### Sample Explanation 2 空間の次元数が $ 4 $ 以上な場合もあります。 ### Constraints - $ 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 $ ) - 入力は全て整数