eolymp
bolt
Try our new interface for solving problems
Problems

Folded Map

Folded Map

Time limit 1 second
Memory limit 128 MiB

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 Cartographic Publishing 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.

Two of many possible ways of tiling Texas-shaped region:

prb6614

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 data

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] (1A[x]1000) give the input image resolution in pixels, while T[r] and T[c] (1T[x]100) is the size of one tile in pixels. 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 data

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

Examples

Input example #1
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.........
Output example #1
4
3
10
Source 2013 ACM ICPC Czech Technical University (CTU) Open Contest, Prague, Problem B