Liquid Cats

Time limit1sMemory limit64 MB

Summary

Given an n by m grid with walls and empty cells, find the lowest row that can be the top of a connected k-cell region of empty cells, or -1 if none exists.

Level: Medium7 of 10
Topics: Binary search, BFS, DFS, Implementation
Solved: No attempts yet

Problem

It is well known that when cats get into a hollow vessel they demonstrate properties of a liquid.

Mathematician Petrov often observed this phenomenon by example of his cats and even conducted a series of experiments constructing different kinds of vessels and putting cats into them. It turned out that cats always choose their position to be as low as possible, more precisely, to minimize the level of the highest point of their body. In case of several pits in the vessel, cats choose the lowest one, but only from those in which they would fit.

A brilliant thought came into Petrov's head: in fact, cats can be used as analog computers for solving some problems of quantum optimization! To check his hypothesis, mathematician Petrov developed the following mathematical model:

Let's imagine a vessel as a table $T$ of size $n \times m$ . Some cells are walls, the rest of the cells are empty. A placement of a cat in the vessel is optimal if the following conditions are met:

The cat occupies several empty cells. All of the cells occupied by the cat form a connected shape of $k$ cells. A shape is connected if each of its cells can be reached from any other cell by moving through adjacent by-side cells (and all the transitional cells are also occupied by the cat).
The level of the highest cell $h$ occupied by the cat should be as low as possible. Rows of the table are numbered from $1$ to $n$ , and a row is higher if its number is less.

Unfortunately, mathematician Petrov is not skilled in programming. He asks you to determine the height of the highest cell $h$ occupied by a cat for a given table $T$ and a cat's volume $k$ .

Input

The first line contains integers $n$ , $m$ , and $k$ ( $1 \le n,m \le 1000$ , $1 \le k \le 10^6$ ).

The following $n$ lines contain $m$ symbols each, a description of table $T$ . The $j$ -th symbol of the $i$ -th row corresponds to a cell on intersection of the $i$ -th row and the $j$ -th column of $T$ . "\#" means that this cell is a wall, and "." means that this cell is empty.

Output

Output the number of a row which contains the highest occupied cell for any optimal placement of a cat. If a cat cannot be placed in the vessel, output "-1" (without quotes).

Notes

An optimal placement of a cat for each sample can be the following:

Examples3

Example 1

Input

6 11 7
...........
.......#...
.......#...
#......#...
########...
#######..##

Expected output

Example 2

Input

6 11 15
...........
.......#...
.......#...
#......#...
########...
#######..##

Expected output

Example 3

Input

5 11 30
..#......##
...........
......#....
......#....
......#....

Expected output