Hamster Cage

Time limit2sMemory limit1024 MB

Summary

Place two cube figures on a table, with rotations and flips allowed, so the region a hamster can reach without escaping is as large as possible.

Level: Medium7 of 10
Topics: Brute force, Simulation, BFS
Solved: No attempts yet

Statement

Andrew received a hamster for his birthday. Until he buys a cage, he wants to build one from spare materials, using a set of cubes he got last year. His sister glued all the cubes together with super glue, so they cannot be separated.

The cubes form two figures. In each figure, any two cubes either share no points, share a face, or share an edge. If they share an edge, some cube shares a face with both of them. Each figure can be placed on a table so that every cube touches the table with one of its faces.

Now Andrew wants to place the two figures on the table to make a hamster cage. Every cube must touch the table with a bottom face, and the sides of the bottom faces must be parallel to the sides of the table. Any two cubes from different figures must either not touch, share a face, or share an edge. Figures may be rotated and flipped.

After placing the figures, Andrew releases the hamster on the table. To keep it from falling off, there must be no path from the release point to the edge of the table. The hamster cannot climb over cubes, and it cannot squeeze between two cubes that share an edge. The table is much larger than either figure.

Andrew wants the area the hamster can roam to be as large as possible. Find the maximum area of the region the hamster can reach. The area of one cube face is 1. If no cage can be built, the answer is 0.

For example, the two figures shown above can be placed as in the next picture. If the hamster is released at the point marked by the arrow, the region it can reach has area 4.

Input

The first line contains two integers $h_1$ and $w_1$ ( $1 \le h_1, w_1 \le 10$ ). The next $h_1$ lines contain $w_1$ characters each and describe the first figure from above. Each character is either * (a cube) or . (an empty cell).

The next line contains two integers $h_2$ and $w_2$ ( $1 \le h_2, w_2 \le 10$ ). The next $h_2$ lines describe the second figure in the same format.

Each figure is connected and contains at least one cube.

Output

Print one integer, the maximum area the hamster can reach. If no cage can be built, print 0.

Examples1

Example 1

Input

8 8
........
.***....
..**....
.*****..
...*.*..
...***..
****....
........
8 8
........
........
........
........
*******.
........
........
........

Expected output