Andres Iniesta

Time limit1sMemory limit128 MB

Summary

You remove up to K obstacles and choose a standing cell to maximize visible cells in its row and column.

Level: Medium5 of 10
Topics: Brute force, Prefix sum, Matrix
Solved: No attempts yet

Problem

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.

Input

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.

Output

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

Constraints

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

Hint

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.

Examples3

Example 1

Input

7 4 5
***.
**.*
..*.
**.*
****
*.**
****

Expected output

Example 2
Input
```
1 1 0
.
```
Expected output
```
1
```
Example 3
Input
```
1 3 1
.*.
```
Expected output
```
3
```