MaxComp

행렬에서 세포들의 부분집합 $S$가 연결되어 있다는 것은, $S$의 임의의 두 세포 사이에 $S$에 속한 세포들만으로 이루어진 경로가 존재한다는 뜻이다. 경로는 세포들의 나열 $u_1, u_2, \ldots, u_k$이며, 모든 $i = 1, \ldots, k-1$에 대해 $u_i$와 $u_{i+1}$은 인접하다.

$N$개의 행과 $M$개의 열로 이루어진 행렬 $A$가 주어질 때, $A$의 연결된 부분집합 $S$에 대해 다음 값을 정의한다.

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

여기서 $|\*|$는 집합의 크기이고, $A(s)$는 행렬 $A$에서 세포 $s$의 값이다.

첫째 줄에 행렬 $A$의 크기를 나타내는 두 수 $N$과 $M$이 주어진다.

다음 $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$

최적의 연결된 부분집합 중 하나는 $\{(1,1),(1,2),(2,2)\}$이다. $\{(1,1),(2,2)\}$는 $(1,1)$과 $(2,2)$ 사이에 경로가 없으므로 답이 될 수 없다.