New Fountain

Today Lorelin was walking through Alfa when she found a new fountain that will open soon and be filled with water. She wondered how much water the fountain can hold.

The fountain is a set of pillars. Its base is an $n \times m$ rectangular grid divided into $nm$ unit squares. Rows are numbered 1 to $n$ and columns 1 to $m$. Each cell holds a pillar of positive integer height, and the pillar in row $i$, column $j$ has height $h_{i,j}$.

When the fountain opens, water pours in from above and fills every empty space inside it. Formally, once the fountain opens, each pillar gets a column of water of some non-negative height, possibly zero. Let $w_{i,j}$ be the water height on the pillar in row $i$, column $j$. Water does not flow out of the fountain if these conditions hold:

• If $i \in \{1, n\}$ or $j \in \{1, m\}$, then $w_{i,j} = 0$. In other words, pillars on the border carry no water, and water drains out of the fountain.
• If $|i_1 - i_2| + |j_1 - j_2| = 1$, then either $w_{i_1,j_1} = 0$ or $h_{i_1,j_1} + w_{i_1,j_1} \le h_{i_2,j_2} + w_{i_2,j_2}$. In other words, a pillar that holds water has a total height no greater than each of its side neighbors.

The total water volume is the sum of all $w_{i,j}$. The fountain fills so that this total is as large as possible.

Lorelin remembers the base size and every pillar height, but she cannot work out the volume. Help her compute it.

The first line contains two integers $n$ and $m$, the number of rows and columns of the base ($3 \le n, m \le 900$). Each of the next $n$ lines contains $m$ integers. Line $i + 1$ contains $h_{i,1}, h_{i,2}, \dots, h_{i,m}$, the heights of the pillars in row $i$ ($1 \le h_{i,j} \le 10^9$).

Print a single number: the maximum total volume of water that can fit in the fountain.

In the first test, the maximum volume is reached with $w_{2,2} = 2$, $w_{2,3} = 1$, and $w_{i,j} = 0$ for all other pillars. These values clearly satisfy all the conditions, and the total volume is 3.

In the second test, only two pillars can hold water. The maximum volume is reached with $w_{2,2} = 1$, $w_{2,3} = 1$, and $w_{i,j} = 0$ for all other pillars. The total volume is 2.