410546: GYM104048 G Foil Folding

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?

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 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$$$).

5 5 3 3
...X.
XX...
..X..
X...X
.X.X.

4