Counting Cross Shapes in a Grid

Interview

Time limit1sMemory limit1024 MB

Summary

Count the cells of an N by M binary grid that center a cross of size K, meaning all cells K steps up, down, left, and right are 1.

Level: Easy3 of 10
Topics: Matrix, Prefix sum, Implementation
Solved: No attempts yet

Problem

Ku colors cells of an $N\times M$ grid in any pattern. While coloring, Ku wondered how many crosses of a given size appear in the grid.

For a cell $(r, c)$ , a cross of size $K$ exists at that cell if the cells from $(r-K, c)$ to $(r+K, c)$ and the cells from $(r, c-K)$ to $(r, c+K)$ are all colored in a row.

The crosses of sizes $0$ , $1$ , and $2$ are shown in the figure below. Count the crosses of size $K$ .

Input

The first line contains the grid size $N$ and $M$ , separated by a space. $\left(1\leq N, M\leq 2,500\right)$

The second line contains the cross size $K$ . $\left(0\leq K\leq \left\lfloor\frac{min(N-1,\,M-1)}{2}\right\rfloor\right)$

From the third line onward, the next $N$ lines give the coloring of the grid, with values separated by spaces. A value of 1 means the cell is colored, and 0 means it is not.

Output

Print the number of crosses of size $K$ .

Examples1

Example 1

Input

5 6
1
0 1 0 1 1 0
1 1 1 1 1 1
0 1 1 1 1 0
0 0 1 0 1 0
1 0 1 1 1 1

Expected output