对于一个矩阵，如果一个单元格集合 $S$ 中的任意两个单元格之间都存在一条仅由 $S$ 中的单元格组成的路径，则称该集合 $S$ 是连通的。路径是指一个单元格序列 $u_1, u_2, \dots, u_k$，其中对于任意 $i = 1, k - 1$，单元格 $u_i$ 和 $u_{i+1}$ 相邻。

给定一个 $N$ 行 $M$ 列的矩阵 $A$，我们为 $A$ 的连通子集 $S$ 定义如下公式：

$$weight(S) = \max\{A(s) | s \in S\} - \min\{A(s) | s \in S\} - |S|$$

其中 $|*|$ 表示集合的基数，$A(s)$ 表示矩阵 $A$ 中单元格 $s$ 的值。

输入格式

第一行包含两个整数 $N$ 和 $M$，表示矩阵 $A$ 的维度。

接下来的 $N$ 行描述该矩阵。第 $i$ 行包含 $M$ 个整数，其中第 $j$ 个值表示 $A(i,j)$。

输出格式

输出给定矩阵中所有连通子集 $S$ 的 $weight(S)$ 的最大值。

数据范围

• $0 \le A(i,j) \le 10^9$
• $1 \le N, M \le 10^3$

子任务

• 对于 15 分：$1 \le N * M \le 20$
• 对于另外 15 分：$N = 1$
• 对于另外 30 分：$N, M \le 50$

样例

样例输入 1

2 3
2 4 3
5 7 5

样例输出 1

2

说明

其中一个最优连通子集是 $\{(1,1),(1,2),(2,2)\}$。$\{(1,1),(2,2)\}$ 不是一个可行解，因为在 $(1,1)$ 和 $(2,2)$ 之间不存在路径。