天上有多少颗星星?年轻的程序员 Polycarpus 无法摆脱这个问题!他用数码相机拍了一张星空照片,现在他分析了所得的单色数码照片。图片由一个由 n 行组成的矩形矩阵表示,每行包含 m 个字符。如果相应的照片像素为白色,则字符等于“1”;如果相应的照片像素为黑色,则字符等于“0”。
Polycarpus 认为,如果他发现一个白色像素被四个同样是白色的侧面相邻像素包围,他就在照片上找到了一颗星星:
1 111 1 照片上有一颗星星
Polycarpus 要从照片中剪出一个矩形区域并送给他的妈妈作为礼物。该区域应包含不少于 k 颗星。星星可以相交,在照片上共享白色像素。男孩将剪切矩形区域,使其边界与照片的侧面平行,并且剪切将直接在像素边界之间进行。
现在,Polycarpus 一直想知道有多少种方法可以从照片中剪切出一个区域,使其满足上面给出的条件。帮助波利卡普斯找到这个号码。
输入
输入数据的第一行包含三个整数n、m和k(1≤n,m≤500;1≤k≤nm)。然后按照 n 行,包含给定照片的描述作为一系列行。每行包含 m 个字符“0”或“1”。
输出
在给定照片上打印所需数量的区域。
示例
输入 #1
4 6 2 111000 111100 011011 000111
输出 #1
6
输入 #2
5 5 4 11111 11111 11111 11111 11111
输出 #2
9
注意
我们将从 1 开始对下面的行和列进行编号,坐标 (p, q) 将表示 p 行 q 列中的单元格。
在第一个样本中,Polycarpus 应切掉包含对角位于单元格 (1, 1) 和 (3, 4) 中的矩形的任何区域。只有对角在 (1, 1) 和 (x, y) 中的矩形,其中 x ≥ 3 且 y ≥ 4 符合条件。
在第二个示例中,任何每边不少于四条的矩形都可以。可能的矩形尺寸为 4 × 4、4 × 5、5 × 4 和 5 × 5。这些图形可以相应地以 4 路、2 路、2 路和 1 路切割。
请不要使用 %lld 说明符在 C++ 中读取或写入 64 位整数。最好使用 cin、cout 流或 %I64d 指定器。