Hasan is bored, and he wants to entertain himself by thinking about complex grid problems.

He randomly generates an \(\mathbf{N} \times \mathbf{M}\) grid that consists of integers. He then decides to transform this grid into an exactly increasing grid. An exactly increasing grid is a matrix whose each cell is greater than its top and left neighbors' values by exactly one. So, if a cell's value \(\mathbf{GRID_{i,\ j}}\) is \(X\), the top and left neighbors of the cell \(\mathbf{GRID_{i - 1,\ j}}\), \(\mathbf{GRID_{i,\ j - 1}}\) should have \(X-1\) as their values.

Hasan wants to convert the grid to an exactly increasing grid by making the minimum number of changes to the grid. To complete his goal he requests help from his friend Ozi. In each change, Ozi can replace an integer in the grid with any integer he wants. Note that Ozi can turn an integer value in the grid into any integer value he likes, including negative integers and 0.

Input

In the first line, integers \(\mathbf{N}\), \(\mathbf{M}\) are given. Those are the given grid's dimensions.

In the following \(\mathbf{N}\) lines the \(\mathbf{N} \times \mathbf{M}\) grid is given. This is the grid Hasan wants to change.

• \(1 \leq \mathbf{N,\ M} \leq 500\)
• \(-10^5 \leq \mathbf{GRID_{i,\ j}} \leq 10^5\)

Output

The minimum number of changes in the grid to transform it to an exactly increasing grid.

Examples

Input 1:

3 3
5 6 7
1 2 3
3 2 1

Output 1:

6

Input 2:

4 3
1 2 3
3 3 4
3 4 4
4 5 6

Output 2:

2

Explanation

Input 1

Ozi can replace the elements in the first row with 0 1 2, and the elements in the third row with 2 3 4. This way all of the rows and columns would be in increasing order. In this way, he would make 6 changes to the initial grid.

Input 2

Ozi can replace the first number on the second row from 3 to 2 and the last number on the third row from 4 to 5. In the end, he would make 2 changes to the initial grid.