P13647 [NOISG 2016] Fabric

Kraw the Krow has a beautiful piece of fabric. The patterns are so intricate that every part of the fabric is different. However, after the Great Fire of 2017, the fabric now has a lot of unsightly holes. (The Great Fire was started, of course, by none other than Squeaky the Rat.) Kraw wants to forget about the Great Fire, because he doesn’t like heat very much. He would like to cut out a rectangle of fabric and throw the rest away. The new piece of fabric must have an area of at least $K$ and cannot contain any holes. Due to the gauge-antisymmetric properties of Kraw’s fabric (or something – Kraw can’t remember what the salesman said), Kraw can only cut the fabric along regular gridlines. Kraw wonders how many ways there are to cut a rectangle with an area of at least $K$ out of the fabric such that it contains no holes.

Your program should read the input from standard input. The input consists of: - one line with three integers $N$ and $M$ ($1 \leq N, M \leq 2000$), the height and width of the fabric, and $K$ ($1 \leq K \leq MN$), the minimum area of the rectangle in terms of the number of grid segments it must contain; - $N$ lines each with $M$ integers $s_{0y}, s_{1y}, \ldots, s_{(M-1)y}$. $s_{xy}$ is $1$ if there is a hole on the segment with coordinates $(x, y)$, and $0$ if there is no hole.

Output one line with a single integer: the number of ways to cut a rectangle with an area of at least $K$ out of the fabric such that it contains no holes.

### Sample Explanation 3 rectangles with an area of at least 3 can possibly be cut from the fabric. Taking the top left segment as $(0, 0)$, there are: - 2 rectangles of area 3 — $\{(1, 0), (2, 0), (3, 0)\}$, $\{(0, 1), (1, 1), (2, 1)\}$ - 1 rectangle of area 4 — $\{(1, 0), (2, 0), (1, 1), (2, 1)\}$ ### Subtasks The maximum execution time on each instance is 1.0s. Your program will be tested on sets of input instances as follows: | Subtask | Marks | Restrictions | | :-: | :-: | :-: | | 1 | 7 | Each instance satisfies $0 < N, M \leq 2000$, $K = 1$ and $s_{xy} = 0$ for all $(x, y)$; | | 2 | 9 | Each instance satisfies $0 < N, M \leq 2000$, $K = 1$ and $s_{xy} = 1$ for only one $(x, y)$; | | 3 | 12 | Each instance satisfies $0 < N, M \leq 50$; | | 4 | 14 | Each instance satisfies $0 < N, M \leq 500$; | | 5 | 23 | Each instance satisfies $0 < N, M \leq 2000$ and $K = 1$; | | 6 | 35 | Each instance satisfies $0 < N, M \leq 2000$. |