G. Foil Folding
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard 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 \lt k \lt 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$$$).

Example
Input
5 5 3 3
...X.
XX...
..X..
X...X
.X.X.
Output
4