20240317
描述
有 n 行 m 列共 n \times m 个坑,每个坑可能有一个萝卜,也可能没有。
现在超能侠需要至少拔 k 个萝卜,他只能挑一个矩形(长方形或正方形)区域的坑进行拔萝卜。
请你求出,为了至少拔 k 个萝卜,他需要挑的矩形面积(坑的数量)最小是多少。
输入
第一行为三个整数 n, m, k。
第二行至第 n + 1 行,每行 m 个只可能为 0 或 1 的整数。其中第 i + 1 行的第 j 个整数为 a _ {i, j},代表第 i 行第 j 列的坑中是否有萝卜。a _ {i, j} = 1 代表有萝卜,a _ {i, j} = 0 代表没有萝卜。
对于 100\% 的数据,保证 1 \leq n, m \leq 20,1 \leq k \leq 400。
输出
输出共一行一个整数,代表为了至少拔 k 个萝卜,超能侠需要挑的矩形的最小面积。
如果所有萝卜的数量都不到 k 个,则输出-1.
样例
输入
5 5 7 0 0 0 1 0 0 0 1 1 1 0 1 1 1 1 0 1 1 0 0 0 0 0 0 1
输出
8