A72 - Tile Painting Editorial /

Time Limit: 1 sec / Memory Limit: 1024 MB

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