시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 512 MB111100.000%

## 문제

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 u1, u2, ..., uk where ui and ui+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.

## 입력

The 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).

## 출력

Print the maximum value of weight(S) between all connected components S of the given matrix.

## 제한

• 0 ≤ A(i,j) ≤ 109
• 1 ≤ N, M ≤ 103

## 예제 입력 1

2 3
2 4 3
5 7 5


## 예제 출력 1

2


## 힌트

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 (1,1) and (2,2).