C. Public Transportation
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

The project of a new city involves the construction of a grid of size $$$n \times m$$$ cells. A house with $$$t_{i,j}$$$ residents will be located at the intersection of the $$$i$$$-th row and the $$$j$$$-th column.

Three houses in cells $$$(i, j)$$$, $$$(i + a, j)$$$ and $$$(i, j + b)$$$ form a good triangle suitable for a public transportation line if:

  • $$$a \gt 0$$$ and $$$b \gt 0$$$;
  • in the house $$$(i, j)$$$, exactly $$$a + b$$$ residents live;
  • in the house $$$(i + a, j)$$$, exactly $$$b$$$ residents live;
  • and in the house $$$(i, j + b)$$$, exactly $$$a$$$ residents live.

You can change the construction plan by increasing or decreasing all $$$t_{i,j}$$$ by the same integer $$$d$$$. If $$$t_{i,j}$$$ should become less than zero, consider it to be equal to zero. Let $$$T + d$$$ denote the matrix of values $$$t_{i,j} + d$$$, and let $$$\triangle(T + d)$$$ be the number of good triangles when the city is constructed accordingly.

Find $$$$$$\sum\limits_{d=-\infty}^{+\infty} \triangle(T + d) \text{,}$$$$$$ or in other words, the total number of good triangles for all possible construction plans.

Input

The first line of input contains two integers $$$n$$$ and $$$m$$$ separated by a space, representing the number of rows and columns of the grid, respectively ($$$1 \le n, m \le 1000$$$).

In the $$$i$$$-th of the following $$$n$$$ lines, there are $$$m$$$ integers $$$t_{i,j}$$$ listed, representing the number of residents in each house of the $$$i$$$-th row of the grid ($$$1 \le t_{i,j} \le 10^9$$$).

Output

Output a single integer, the number of sets of three cells that satisfy the given conditions.

Scoring

Points for each subtask are awarded only if all tests of this subtask and the necessary subtasks are successfully passed.

SubtaskPointsConstraintsRequired subtasks
0–examples from the statement
18$$$t_{i,j} \le 2$$$ for all $$$i$$$, $$$j$$$
213$$$n \le 2$$$
317$$$n, m \le 50$$$, $$$t_{i,j} \le 50$$$0
417$$$n, m \le 500$$$0, 3
520$$$t_{i,j}$$$ are generated randomly and uniformly0
625none0 – 5
Examples
Input
3 3
3 1 1
1 2 1
1 1 1
Output
2
Input
2 4
5 4 3 2
4 3 2 1
Output
6
Note

In this problem the input data size is large so it may be useful to use fast IO.