Problem Background

lanzerb's tribe is located in the upper part of country A. Dissatisfied with the harsh environment, they plan to wage war on the lower part of country A to acquire more territory.

Problem Description

Country A is represented as an $M \times N$ matrix, where some areas are towns and others are uninhabited due to high mountains and deep ravines. lanzerb has divided his tribe into several armies, with the following agreements:

• Each army can start from any town and can only move downwards, without turning back. They can only pass through towns and must not pass through high mountains and deep ravines.
• If a town has been visited by one army, it cannot be visited by another army.
• Each army can stop its campaign at any town.

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

lanzerb's ambition is to unify the entire country, but the limitation of troops makes it difficult to allocate manpower. Assuming that each army can successfully occupy all the towns it passes through, please calculate the minimum number of armies needed to achieve the goal of unifying the country.

Input Format

The first line contains four integers $M, N, R, C$, as described in the problem. The next $M$ lines each contain a string of length $N$. If a character is ., it indicates a town; if it is x, it indicates a high mountain or deep ravine.

Output Format

Output a single integer, representing the minimum number of armies required.

Sample Input and Output

Sample Input #1

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

Sample Output #1

4

Sample Input #2

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

Sample Output #2

5

Notes

Data Size and Constraints

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

见题面 Input 部分

见题面 Output 部分