题目描述

“聚合什么，要看缘份”。

云小斗想送你两朵不具名的花。然而 ta 在采花的时候迷了路，于是情况又变成了你要自己去寻找送给你自己的礼物。

具体来讲，宇宙中每一朵花拥有一个 $d$ 维坐标 $(x_1,x_2,x_3,\ldots,x_d)$。云小斗给你划定了一个范围，范围里共有 $n$ 朵花。ta 想送给你范围里两朵不具名的花——也就是所有花里距离最远的两朵花。

空间里两朵花 $P(x_1,x_2,x_3,\ldots,x_d)$ 和 $Q(y_1,y_2,y_3,\ldots,y_d)$ 之间的距离定义为：

$dist(P,Q)=\sum_{i=1}^d |y_i-x_i| = |y_1-x_1|+|y_2-x_2|+\cdots+|y_d-x_d|$

其中 $|a|$ 表示 $a$ 的绝对值。

现在云小斗给出了范围里所有花的坐标，请你求出两朵不具名的花间的距离是多少。

输入格式

从文件 noname.in 中读入。

第一行包含两个正整数 $n,d$，分别表示点的个数和空间的维度。

接下来 $n$ 行，每行包含 $d$ 个整数 $x_{i,1},x_{i,2},x_{i,3},\ldots,x_{i,d}$，表示第 $i$ 朵花在 $d$ 维空间里的各维度坐标。

输出格式

输出到文件 noname.out 中。

输出一个整数，表示两朵不具名的花之间的距离。

输入输出样例

输入样例 1

4 1
2
1
4
5

输出样例 1

4

样例 1 说明

四朵花的一维坐标分别为 $2,1,4,5$。

距离最远的两朵花坐标为 $1$ 和 $5$，它们之间的距离为 $|5-1|=4$。

输入样例 2

4 2
2 1
1 4
4 5
5 3

输出样例 2

6

样例 2 说明

四个点分别为 $(2,1)$、$(1,4)$、$(4,5)$、$(5,3)$。

例如点 $(2,1)$ 与点 $(4,5)$ 之间的距离为：

$|4-2|+|5-1|=2+4=6$

这是所有点对中的最大值，因此答案为 $6$。

样例 3

见下发文件中的 noname3.in 与 noname3.out。

样例 4

见下发文件中的 noname4.in 与 noname4.out。

数据范围和约定

• 对于前 $20\%$ 的数据，保证 $1\le n\le 2000$；
• 对于前 $40\%$ 的数据，保证 $1\le n\le 5\times 10^4$；
• 对于另外 $20\%$ 的数据，满足 $1\le d\le 2$；
• 对于另外 $10\%$ 的数据，满足 $0\le x_{i,j}\le 20$；
• 对于 $100\%$ 的数据，满足 $1\le n\le 2\times 10^5$，$1\le d\le 8$，$0\le x_{i,j}\le 10^6$。