配点: 1000 点
問題文
縦 H 行、横 W 有一个列网格。从上面 i 行/从左起 j 柱方 (i, j) 的颜色是 c_{i,j} 和c_{i,j} = . , c_{i,j} = # 被漆成黑色。
您正在执行操作“选择特定行或列并将它们重新绘制为黑色。” 您最多可以执行 K 次。你能把多少个方格变成黑色?
制約
- 1 \leq H \leq 10
- 1 \leq W \leq 100
- 1 \leq K \leq \min(H, W)
- c_{i, j} 是
您也可以写
.或 至少#是
入力
输入是按以下格式从标准输入给出的。
H W K
c_{1, 1} c_{1, 2} \cdots c_{1, W}
\vdots
c_{H, 1} c_{H, 2} \cdots c_{H, W}
出力
请输出可以变黑的最大方块数。 满足
入力例 1
4 10 3 ##...#.##. .#....#... ##.####..# #..######.
出力例 1
37