← 返回题目列表

AtCoder · tessoku_book_bt

A72. 瓷砖画

中文机器翻译题面 查看原题

配点: 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