开始: 2024-03-17 14:30:00

20240317

结束: 2024-03-17 17:30:00
当前: 2025-0505-3131 13:20:58  类型:单人排位赛 状态:已经结束 
P5 : A-拔萝卜  
描述

nm 列共 n \times m 个坑,每个坑可能有一个萝卜,也可能没有。 
现在超能侠需要至少拔 k 个萝卜,他只能挑一个矩形(长方形或正方形)区域的坑进行拔萝卜。 
请你求出,为了至少拔 k 个萝卜,他需要挑的矩形面积(坑的数量)最小是多少。 

输入

第一行为三个整数 n, m, k。 
第二行至第 n + 1 行,每行 m 个只可能为 01 的整数。其中第 i + 1 行的第 j 个整数为 a _ {i, j},代表第 i 行第 j 列的坑中是否有萝卜。a _ {i, j} = 1 代表有萝卜,a _ {i, j} = 0 代表没有萝卜。 

对于 100\% 的数据,保证 1 \leq n, m \leq 201 \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