Maximum Rides on Grid

You are given a grid with n rows and m columns. Each cell in the grid is either open (denoted by .) or blocked (denoted by #). A ride can be placed in a column if there exists at least one contiguous segment of open cells with length at least k. Formally, for a column, if there exists an index i such that:

[ \sum_{j=0}^{k-1} I{grid[i+j] = '.'} = k ]

where \(I\{\cdot\}\) is the indicator function, then a ride can be placed in that column. Your task is to determine the maximum number of rides that can be placed, which is equal to the number of columns that satisfy this condition.

Note: The ride is placed in a column only once regardless of how many segments meet the requirements, so you only count the column once.

inputFormat

The first line contains three integers n, m, and k (1 ≤ n, m ≤ 1000, 1 ≤ k ≤ n), representing the number of rows, the number of columns, and the minimum continuous open cells required to place a ride respectively.

Then follow n lines, each containing a string of length m composed only of the characters . (open cell) and # (blocked cell), describing the grid.

outputFormat

Output a single integer, the maximum number of rides that can be placed on the grid.

5 5 3
.....
.#.#.
.#.#.
.....
#####

3