Fabric — Eolymp

Input

The first line contains three integers $n$ , $m$ , and $k$ ( $1 \leq n, m \leq 2000$ 1 \le n, m \le 2000, $1 \leq k \leq n \cdot m$ 1 \le k \le n \cdot m) — the height and width of the fabric, and the minimum area of the desired rectangle.

The next $n$ lines contain $m$ numbers each, describing the fabric. In the $i$ -th row, the numbers are $s_{i 1}, s_{i 2}, \dots s_{im}$ s_{i 1}, s_{i 2}, \dots s_{i m}.

$s_{x y}$ s_{x y} equals $1$ if the patch at coordinates $(x, y)$ has a hole, and $0$ if it does not.

Output

Output a single line with one integer: the number of ways to cut a rectangle with an area of at least $k$ such that it does not contain any holes.

Examples

Example 1

Loading

Note

$3$ rectangles with an area of at least $3$ can be cut from the fabric. If we take the top left square as $(0, 0)$ , the possible options are:

$2$ rectangles with an area of $3$ :
- ${(1, 0), (2, 0), (3, 0)}$ \{(1, 0), (2, 0), (3, 0)\}
- ${(0, 1), (1, 1), (2, 1)}$ \{(0, 1), (1, 1), (2, 1)\}
$1$ rectangle with an area of $4$ :
- ${(1, 0), (2, 0), (1, 1), (2, 1)}$ \{(1, 0), (2, 0), (1, 1), (2, 1)\}

Scoring

(56 points): $1 \leq n, m \leq 2000$ 1 \le n, m \le 2000, $k = 1$ k = 1 and $s_{x y} = 0$ s_{xy} = 0 for all $(x, y)$ ;
(72 points): $1 \leq n, m \leq 2000$ 1 \le n, m \le 2000, $k = 1$ k = 1 and $s_{x y} = 1$ s_{xy}=1 only for one patch $(x, y)$ ;
(96 points): $1 \leq n, m \leq 50$ 1 \le n, m \le 50;
(112 points): $1 \leq n, m \leq 500$ 1 \le n, m \le 500;
(184 points): $1 \leq n, m \leq 2000$ 1 \le n, m \le 2000 and $k = 1$ k = 1;
(280 points): $1 \leq n, m \leq 2000$ 1 \le n, m \le 2000.