MAXCOMP#8726
Sign in

MAXCOMP

0.5 seconds
256 megabytes
Very easy

For a matrix, let's call a subset of cells, , connected if there is a path between any two cells of which consists only of cells from . 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, \ldots, k-1.

Given a matrix with rows and columns, we define the following formula for a connected subset of :

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

where represents the cardinality of a set and represents the value of the cell in .

Input

The first line of input contains two numbers and representing the dimensions of the matrix .

The following lines describe the matrix. The -th line contains integers where the -th value represents A(i,j).

Constraints: 0 \le A(i,j) \le 10^9, 1 \le N, M \le 10^3.

Output

Print the maximum value of between all connected components of the given matrix.

Examples

Example 1

Loading
Loading

Note

One 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 and .

Scoring

* For 15 points: 1 \le N \cdot M \le 20 * For other 15 points: N = 1 * For other 30 points: N, M \le 20