Description

Kraw the Krow 有一块漂亮的布料。布料上的花纹非常精致，以至于每一部分都不相同。然而，在 2017 年的大火之后，这块布料上出现了许多难看的洞。（当然，这场大火是由 Squeaky the Rat 引发的。）

Kraw 想要忘记那场大火，因为他并不喜欢高温。他希望能从布料上裁剪出一个矩形，把剩下的部分都扔掉。新的布料必须满足面积至少为 $K$，并且不能包含任何洞。

由于 Kraw 的布料具有“规-反对称”特性（或者别的什么——Kraw 已经不记得推销员说了什么），Kraw 只能沿着规则的网格线裁剪布料。Kraw 想知道，有多少种方法可以裁剪出一个面积至少为 $K$、且不包含任何洞的矩形。

Input Format

你的程序应从标准输入读取数据。输入包括：

• 一行，包含三个整数 $N$ 和 $M$（$1 \leq N, M \leq 2000$），分别表示布料的高度和宽度，以及 $K$（$1 \leq K \leq MN$），即矩形的最小面积（以网格单元数计）；
• 接下来 $N$ 行，每行包含 $M$ 个整数 $s_{0y}, s_{1y}, \ldots, s_{(M-1)y}$。若坐标为 $(x, y)$ 的网格单元有洞，则 $s_{xy} = 1$，否则 $s_{xy} = 0$。

Output Format

输出一行，包含一个整数：表示可以裁剪出多少种面积至少为 $K$、且不包含任何洞的矩形。

2 4 3
1 0 0 0
0 0 0 1

3

Hint

样例解释

可以从布料上裁剪出 3 个面积至少为 3 的矩形。以左上角为 $(0, 0)$，它们分别是：

• 2 个面积为 3 的矩形——$\{(1, 0), (2, 0), (3, 0)\}$，$\{(0, 1), (1, 1), (2, 1)\}$
• 1 个面积为 4 的矩形——$\{(1, 0), (2, 0), (1, 1), (2, 1)\}$

子任务

每组数据的最大运行时间为 1.0 秒。你的程序将在以下输入范围内进行测试：

由 ChatGPT 4.1 翻译