背景

GESP五级真题(202406)

描述

⼩杨有⼀个 $n$ ⾏ $m$ 列的⽹格图，其中每个格⼦要么是⽩⾊，要么是⿊⾊。

小杨想知道至少包含 $k$ 个黑色格子的最小子矩形包含了多少个格子。

格式

输入

第⼀⾏包含两个正整数 $n,m, k$ ，含义如题⾯所⽰。

之后 $n$ ⾏，每⾏⼀个长度为 $m$ 的 0 1 串，代表⽹格图第 $i$ ⾏格⼦的颜⾊，如果为 0 ，则对应格⼦为⽩⾊，否则为⿊⾊。

输出

输出一个整数，代表至少包含 $k$ 个黑色格子的最小子矩形包含格子的数量，如果不存在则输出 0。

样例

4 5 5
00000 
01111 
00011 
00011

6

样例解释

对于样例1，假设 ($i, j$) 代表第 $i$ 行第 $j$ 列，至少包含 5 个黑色格子的最小子矩形的四个顶点为 ($2,4$)，($2,5$)，($4,4$)，($4,5$)，共包含 6 个格子。

数据规模

对于全部数据，保证有$1 \le n, m \le 100, 1 \le k \le n \times m$。

限制

时间限制：1.0 s

空间限制：512.0 MB