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

Підзадачі

• За 15 балів: 1 ≤ N*M ≤ 20

• За інші 15 балів: N = 1

• За інші 30 балів: N,M ≤ 20

Приклади

Примітка

Однією з оптимальних зв'язаних підмножин є {(1,1),(1,2),(2,2)}. {(1,1),(2,2)} не є рішенням, оскільки немає шляху між (1,1) та (2,2).