Counting Valid Square Pastures

Farmer John needs to determine the number of square pastures (with side length at least 2) that can be used to graze his cows. A square pasture is valid if every cell inside the square is intact (represented by a '1'). Note that the square pastures may overlap.

Let \(dp[i][j]\) denote the side length of the largest valid square ending at cell \((i,j)\). The state transition can be written in \(\LaTeX\) as:

\( dp[i][j] = \min \{ dp[i-1][j],\; dp[i][j-1],\; dp[i-1][j-1] \} + 1 \) if the cell \((i, j)\) is 1, and 0 otherwise.

Your task is to count all valid sub-squares of size at least 2. For every valid square ending at \((i,j)\) with \(dp[i][j] = k \ge 2\), it contributes \(k-1\) squares (of sizes 2, 3, \(\dots\), k).

inputFormat

The first line of input contains two space-separated integers \(n\) and \(m\) representing the number of rows and columns of the grid.

Then follow \(n\) lines, each containing \(m\) space-separated integers (either 0 or 1), representing the grid.

outputFormat

Output a single integer representing the total number of valid square pastures (of size at least 2) that are completely filled with 1's.

sample

3 3
1 1 1
1 1 1
1 1 1

5