Pixel art P38156

En Max ha fet un programa per dibuixar. En obrir l’aplicació, apareix una graella amb $m \times n$ píxels en blanc. A continuació, es poden clicar els píxels d’un en un.

Com que aquest procediment és poc eficient, s’ha afegit una funcionalitat: si s’acaba de pintar el píxel $(x, y)$, aleshores també es pot pintar el píxel $(x+1, y)$, $(x-1, y)$, $(x, y-1)$ o $(x, y+1)$, i així successivament, passant si cal sobre caselles ja pintades, però mai sortint fora de la graella.

Donat el dibuix que voldria pintar en Max, trobeu quin és el màxim nombre de píxels que podrà pintar si només pot clicar $k$ píxels inicials.

Entrada

Les dues primeres línies contenen el color de fons i el color del dibuix. Les tres línies següents contenen $n$, $m$ i $k$. A continuació venen $n$ línies, cadascuna amb $m$ caràcters: punts per píxels en blanc, i ‘X’s per píxels que es voldrien pintar. Podeu suposar $n, m \ge 1$ i $k \ge 0$.

Sortida

Dibuixeu la imatge que tingui el màxim nombre de píxels pintats, clicant com a molt $k$ píxels inicials, i no pintant cap dels píxels en blanc. Amb els jocs de proves donats, la solució serà única.