Coin Puzzle

Interview

Time limit1sMemory limit1024 MB

Summary

Given two coin grids of up to 10 by 10, find the fewest coins to move so the first arrangement becomes the second by translation only.

Level: Easy3 of 10
Topics: Brute force, Implementation
Solved: No attempts yet

Problem

Solve a coin puzzle! At the start, some coins are placed on an infinite grid plane. Every coin sits on a lattice point.

The goal of the puzzle is to create a new shape by moving the fewest possible coins. Each move picks up one coin and places it on an empty lattice point. The new shape may appear at any position, but making a rotated or reflected shape is not allowed.

For example, consider the following two coin arrangements.

To turn the first arrangement into the second, at least four coins must be moved, as shown below.

Given the current coin arrangement and the arrangement to be made, find the minimum number of coins that must be moved.

Input

The first line contains integers $H_1$ and $W_1$ ( $1\le H_1,W_1\le 10$ ). The next $H_1$ lines each contain a string of length $W_1$ . '.' is an empty cell and 'O' is a cell with a coin. This describes the current arrangement of coins.

The next line contains integers $H_2$ and $W_2$ ( $1\le H_2,W_2\le 10$ ). The next $H_2$ lines each contain a string of length $W_2$ , using the same notation. This describes the arrangement of coins to be made.

The two arrangements are guaranteed to have the same number of coins.

Output

Print the minimum number of coins that must be moved.

Examples3

Example 1

Input

5 5
O...O
O...O
OOOOO
..O..
..O..
5 5
..O..
..O..
OOOOO
O...O
O...O

Expected output

Example 2
Input
```
2 5
OOO.O
O.OOO
4 3
.OO
OO.
.OO
OO.
```
Expected output
```
4
```

Example 3

Input

3 5
.O...
OO...
.....
4 3
...
...
..O
.OO

Expected output