410555: GYM104049 G Foil Folding

Memory Limit:256 MB Time Limit:1 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

G. Foil Foldingtime limit per test1 secondmemory limit per test256 megabytesinputstandard inputoutputstandard output

Fo has been folding foil for years now, in the hopes of making their own ingot out of foil!

The foil forms an $$$n$$$ by $$$m$$$ rectangle of metal. Due to human error though, a few air bubbles and other imperfections have accumulated throughout the layers of foil. Thankfully, Fo has diligently marked out where each imperfection is.

To qualify as an ingot, a piece of metal must have one of its dimensions be exactly $$$k$$$. Additionally, Fo has some standards for their ingot, namely that it can only contain at most $$$x$$$ imperfections. Can you help Fo find the biggest ingot?

Input

The first line contains four integers, $$$n$$$, $$$m$$$, $$$k$$$, and $$$x$$$ ($$$1 \leq nm \leq 10^5$$$, $$$1 < k < max(n,m)$$$, $$$k \leq x \leq nm$$$), denoting the size of the sheet of foil.

Then, $$$n$$$ lines follow, each containing $$$m$$$ characters. "X" represents an imperfection in the foil, and "." represents a perfect section of foil.

Output

Output a single integer, the maximum length of an ingot that contains at most $$$x$$$ imperfections. Note that length here corresponds to the dimension that is not $$$k$$$. (A $$$k$$$ by $$$k$$$ ingot has length $$$k$$$).

ExampleInput
5 5 3 3
...X.
XX...
..X..
X...X
.X.X.
Output
4

加入题单

算法标签: