28908번 - Новый фонтан 다국어

Сегодня, прогуливаясь по Альфе, Лорелин обнаружила новый фонтан, который совсем скоро будет открыт и наполнен водой. Лорелин стало интересно, сколько воды будет помещаться в этот фонтан.

Фонтан представляет из себя набор столбиков. Основанием фонтана является прямоугольное поле $n \times m$, разделенное на $nm$ единичных квадратов. Строки основания пронумерованы целыми числами от $1$ до $n$, а столбцы --- целыми числами от $1$ до $m$. В каждой клетке поля расположен столбик целой положительной высоты. Высота столбика, расположенного на пересечении $i$-й строки и $j$-го столбца, составляет $h_{i, j}$.

После открытия фонтана сверху на него будет литься вода до тех пор, пока она не заполнит все возможные пустоты внутри фонтана. Приведем формальное описание заполнения фонтана водой: после того, как фонтан будет открыт, на каждом из столбиков сверху появится столб воды некоторой неотрицательной (но, возможно, нулевой) высоты. Пусть высота столба воды на столбике, расположенном на пересечении $i$-го столбца и $j$-й строки, составляет $w_{i, j}$. Будем говорить, что вода не выливается из фонтана, если выполнены следующие условия:

• Если $i \in \{1, n\}$ или $j \in \{1, m\}$, то $w_{i, j} = 0$. Иными словами, на столбиках, расположенных на границе поля, сверху нет воды: она стекает за пределы фонтана.
• Если $|i_1 - i_2| + |j_1 - j_2| = 1$, то либо $w_{i_1, j_1} = 0$, либо $h_{i_1, j_1} + w_{i_1, j_1} \le h_{i_2, j_2} + w_{i_2, j_2}$. Иными словами, для любого столбика выполнено одно из двух: либо на нем сверху нет воды, либо суммарная высота столбика и столба воды на нем не превышает суммарной высоты столбика и столба воды на каждом из соседних по стороне столбиков.

Общий объем воды, находящейся в фонтане, равен сумме значений $w_{i, j}$ для всех столбиков. Фонтан наполняется водой таким образом, чтобы общий объем воды был максимально возможным.

Лорелин запомнила размеры основания фонтана, а также высоты всех столбиков, из которых он состоит, однако посчитать, какой объем воды будет помещаться в фонтане, она затрудняется. Помогите ей справиться с этой задачей, ведь у самой Лорелин есть куда более полезные дела!

Первая строка входных данных содержит два целых числа $n$ и $m$ --- количество строк и столбцов в основании фонтана ($3 \le n, m \le 900$).

Каждая из следующих $n$ строк содержит по $m$ целых чисел. Строка с номером $i + 1$ содержит числа $h_{i, 1}, h_{i, 2}, \dots, h_{i, m}$ --- высоты столбиков, располагающихся в $i$-й строке ($1 \le h_{i, j} \le 10^9$).

Выведите единственное число --- максимальный общий объем воды, который может поместиться в фонтан.

В первом тесте из условия максимальный объем достигается при $w_{2, 2} = 2$, $w_{2, 3} = 1$, $w_{i, j} = 0$ для всех остальных столбиков. Легко убедиться, что все необходимые условия при этом выполняются, а общий объем воды равен $3$.

Во втором тесте из условия только на двух столбиках может располагаться вода: максимальный объем достигается при $w_{2, 2} = 1$, $w_{2, 3} = 1$, $w_{i, j} = 0$ для всех остальных столбиков. Общий объем воды равен $2$.