MAXCOMP

Для матрицы назовем подмножество ячеек S связанным, если между любыми двумя ячейками из S существует путь, состоящий только из ячеек из S. Путь — это последовательность ячеек u[1], u[2], ..., u[k], где u[i] и u[i+1] смежны для любого i=1,k-1.

Дана матрица A размером N на M. Мы определяем следующую формулу для связанного подмножества S матрицы A:вес(S) = (max{A(s)|s∈S} - min{A(s)|s∈S} - |S|),где |*| обозначает количество элементов в множестве, а A(s) — значение ячейки s в A.

Входные данные

Первая строка входных данных содержит два числа N и M, которые задают размеры матрицы A.

Следующие N строк описывают матрицу. i-я строка содержит M целых чисел, где j-е значение представляет A(i,j).

Выходные данные

Выведите максимальное значение веса(S) среди всех связанных компонент S данной матрицы.

Общие ограничения

0 ≤ A(i,j) ≤ 10^91 ≤ N, M ≤ 10^3

Примеры

Примечание

Одно из оптимальных связанных подмножеств — это {(1,1),(1,2),(2,2)}. {(1,1),(2,2)} не является решением, потому что между (1,1) и (2,2) нет пути.

Оценивание

• На 15 баллов: 1 ≤ N*M ≤ 20

• На другие 15 баллов: N = 1

• На другие 30 баллов: N,M ≤ 20