Description

Country A is an $M \times N$ matrix, where some cells are towns and some are uninhabited mountains and chasms. lanzerb divides his tribe into several armies, with the following rules:

Each army may start from any town and can only advance downward, from top to bottom, without turning back. Along the way, they may pass only through towns, not through mountains and chasms.

If a town has been visited by one army, no other army may visit that town again. Each army may stop at any town.

All the armies move in a way similar to a knight in chess. However, while a knight moves in a $1 \times 2$ pattern, they move in an $R \times C$ pattern.

Driven by ambition, lanzerb aims to unite the entire country, but limited manpower makes staffing difficult. Assuming each army successfully occupies all towns it passes through, please help lanzerb compute the minimum number of armies needed to unify the entire country.

Input Format

The first line contains $4$ integers $M, N, R, C$, as described above. Then follow $M$ lines, each being a string of length $N$. If a character is . it denotes a town; if a character is x it denotes mountains and chasms.

Output Format

Output a single integer, the minimum number of armies.

3 3 1 2
...
.x.
...

4

5 4 1 1
....
..x.
...x
....
x...

5

Hint

Constraints

For $100\%$ of the testdata, $1 \le M, N \le 50$, $1 \le R, C \le 10$.

Translated by ChatGPT 5