Control in a Matrix

You are given an $N \times M$ matrix $A[1..N][1..M]$. We say that $(x_1,y_1)$ controls $(x_2,y_2)$ if and only if $A[x_1][y_1] > A[x_2][y_2] + |x_1-x_2| + |y_1-y_2|$. Now you need to calculate the number of pairs $((x_1,y_1),(x_2,y_2))$ that $(x_1,y_1)$ controls $(x_2,y_2)$.

There are multiple test cases.

For each test case, the first line contains two integers $N$ and $M$, denoting the size of the matrix.

Then there are $N$ lines denoting the matrix, where each line contains $M$ integers.

$1\leq N,M \leq 10^3, ~ 1\leq A[i][j] \leq N+M$. And the sum of $N \times M$ of all test cases is not larger than $2 \cdot 10^6$.

For each test case, print an integer in one line, denoting your answer.

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

18
14

2021“MINIEYE杯”中国大学生算法设计超级联赛-热身赛（2021湘潭全国邀请赛-重现）