MAXCOMP
For a matrix, let’s call a subset of cells, S, connected if there is a path between any two cells of S which consists only of cells from S. A path is a sequence of cells u[1], u[2], ..., u[k] where u[i] and u[i+1] are adjacent for any i=1,k-1
Given a matrix A with N rows and M columns, we define the following formula for a connected subset S of A:weight(S) = (max{A(s)|s∈S} - min{A(s)|s∈S} - |S|).where |*| represents the cardinality of a set and A(s) represents the value of the cell s in A.
####InputThe first line of input contains two number N and M representing the dimensions of the matrix A.
The following N lines describe the matrix. The i-th line contains M integers where the j-th value represents A(i,j).
####OutputPrint the maximum value of weight(S) between all connected components S of the given matrix.
####General constraints0 ≤ A(i,j) ≤ 10^91 ≤ N , M ≤ 10^3
####Subtasks
For 15 points: 1 ≤ N*M ≤ 20
For other 15 points: N = 1
For other 30 points: N,M ≤ 20
####ExplanationOne of the optimal connected subsets is {(1,1),(1,2),(2,2)}. {(1,1),(2,2)} is not a solution because there is no path between (1,1) and (2,2).