Migrated from Lutece 786 Folded Map

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

Freddy's garden became so large that he needs a map to keep evidence of which vegetables are planted in what area. He ordered a high-quality map from the International CartographicPublishing Company (ICPC). Since the map has a large scale, it does not fit onto a single page and it has to be split into several rectangular tiles.

Even with a fixed tile size (determined by a page size) and map scale, the number of tiles may still differ by adjusting the position of the tile grid. Your task is to find the minimal number of tiles necessary to cover the whole region of Freddy's garden.

Let's have a look at an example. The figure on the left shows $14$ map tiles covering a region. By adjusting the grid position a little bit, we may cover the same region with only $10$ tiles, without changing their size or orientation.

Note that the tiles must be part of a rectangular grid aligned with the $x-axis$ and $y-axis$. That is, they touch each other only with their whole sides and cannot be rotated.

Input

The input contains several test cases. The first line of each test case contains four integer numbers: $A_r$ , $A_c$, $T_r$ , and $T_c$. $A_r$ and $A_c$ give the input image resolution in pixels ($1\leq A_x\leq 1000$), while $T_r$ and $T_c$ is the size of one tile in pixels ($1\leq T_x\leq 100$). The next $A_r$ lines each contain $A_c$ characters, each of them being either X (the pixel corresponds to a part of the garden to be covered by a tile) or . (the corresponding pixel is outside the garden and does not need to be covered). The region pixels form one connected region.

Output

For each test case, print one integer number -- the minimal number of tiles necessary to cover all pixels represented by X.

Samples

3 3 2 2
XXX
XXX
XXX
3 3 2 2
XX.
XXX
XXX
17 32 5 9
........XXXXXXXX................
........XXXXXXXX................
........XXXXXXXX................
........XXXXXXXXX...............
........XXXXXXXXXXXXXXX.........
........XXXXXXXXXXXXXXXXXXXX....
........XXXXXXXXXXXXXXXXXXXXX...
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXX..
..XXXXXXXXXXXXXXXXXXXXXXXXXXXXX.
....XXXXXXXXXXXXXXXXXXXXXXXXXXX.
......XXXXXXXXXXXXXXXXXXXXXXXXX.
........XX..XXXXXXXXXXXXXXXXX...
.............XXXXXXXXXXXXXX.....
...............XXXXXXXXX........
................XXXXXXX.........
.................XXXXX..........
....................XXX.........

4
3
10

Resources

CTU Open Contest, 2013