Темпоральные дожди
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Иногда в Пустоте идут темпоральные дожди. Это достаточно необычное событие для места «вне времени», поэтому и последствия тоже значимые — некоторые сосланные в Пустоту существа справлялись выбраться из нее, изучая поведение этих темпоральных дождей.

Если мы представим поверхность Пустоты как координатную решетку размером $$$n \times m$$$ ($$$n$$$ строк и $$$m$$$ столбцов), с уровнем поверхности в ячейке $$$(i, j)$$$ равным $$$h_{i, j}$$$, то после темпорального дождя темпоральная энергия скапливается на этой решетке, как скапливалась бы вода при обычном дожде: если ей некуда перелиться за границы Пустоты, она будет держаться на одном уровне.

Более формально, скажем, что $$$d_{i, j}$$$ — уровень энергии в ячейке $$$(i, j)$$$ — это величина со следующими свойствами:

Иными словами, рассмотрим все пути от ячейки до границы Пустоты (каждый переход на пути — в соседнюю по стороне ячейку), на каждом пути выберем $$$\max$$$ уровня поверхности, и среди всех таких выберем минимальный — это и будет уровень энергии в этой ячейке.

Определите суммарный уровень энергии относительно уровня поверхности, который установится по всей Пустоте после окончания темпорального дождя, чтобы помочь Дэдпулу и Росомахе из нее выбраться.

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

В первой строке даны два целых числа $$$n$$$ и $$$m$$$ — размеры Пустоты ($$$1 \le n, m \le 10^6$$$; $$$1 \le n \cdot m \le 10^6$$$).

В $$$i$$$-й из следующих $$$n$$$ строках перечислены $$$m$$$ чисел $$$h_{i,j}$$$ ($$$0 \le h_{i, j} \le 10^9$$$).

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

Выведите единственное число — $$$\sum\limits_{i, j} (d_{i,j} - h_{i,j})$$$ для удовлетворяющих условию $$$d$$$.

Примеры

Входные данные
5 5
4 4 4 5 4
4 3 5 2 5
3 3 5 3 7
8 8 3 6 0
1 1 3 6 1
Выходные данные
5
Входные данные
3 3
1 3 1
3 1 3
1 3 2
Выходные данные
2