Background

Related multiple-choice and true/false questions: https://ti.luogu.com.cn/problemset/1153.

Problem Description

Xiao Yang has a grid with $n$ rows and $m$ columns, where each cell is either white or black.

Xiao Yang wants to know how many cells are contained in the smallest sub-rectangle that contains at least $k$ black cells.

Input Format

The first line contains three positive integers $n, m, k$, with meanings as described in the statement.

Then follow $n$ lines, each containing a $\texttt{01}$ string of length $m$, representing the colors of the cells in row $i$ of the grid. If it is $\texttt{0}$, the corresponding cell is white; otherwise, it is black.

Output Format

Output one integer, representing the number of cells contained in the smallest sub-rectangle that contains at least $k$ black cells. If it does not exist, output $0$.

4 5 5
00000
01111
00011
00011

6

Hint

Sample Explanation

For sample $1$, let $(i, j)$ represent row $i$ and column $j$. The four vertices of the smallest sub-rectangle that contains at least $5$ black cells are $(2, 4)$, $(2, 5)$, $(4, 4)$, $(4, 5)$, and it contains a total of $6$ cells.

Constraints

For all data, it is guaranteed that $1 \le n, m \le 100$ and $1 \le k \le n \times m$.

Update on 2024/7/9: Several groups of hack testdata were added. Thanks to @cff_0102 for the contribution.

Translated by ChatGPT 5