Andres Iniesta

Midfielder Andres Iniesta trains on an $N \times M$ grid where some cells hold obstacles. He stands on an empty cell and sees every cell in the same row or column with no obstacle between them, including his own cell.

Iniesta can destroy obstacles with a ball, at most $K$ times. After destroying obstacles, find the maximum number of cells he can see from some empty cell. He may stand on a cell that was empty initially or on a cell whose obstacle he destroyed.

The first line contains $N$, $M$, and $K$: the number of rows, columns, and the maximum obstacles he may destroy.

Each of the next $N$ lines has $M$ characters: . for an empty cell and * for an obstacle.

Print one integer: the maximum number of visible cells after destroying up to $K$ obstacles and standing on an empty cell.

• $1 \le N, M \le 200$
• $0 \le K \le 50$

Only obstacles on Iniesta's row and column affect his view from a chosen cell. For each candidate cell, try destroying up to $K$ obstacles on that row and column and count visible cells.