동전 퍼즐

동전 퍼즐을 풀어 보자! 처음에 무한 격자 평면에 동전 몇 개가 놓여 있다. 모든 동전은 격자점 위에 있다.

퍼즐의 목표는 최소 개수의 동전을 옮겨서 새로운 모양을 만드는 것이다. 동전을 옮길 때는 한 번에 한 개씩, 동전을 들어서 빈 격자점에 놓으면 된다. 새로운 모양이 만들어지는 위치는 어디든 상관없지만, 회전된 모양이나 대칭된 모양을 만드는 것은 인정되지 않는다.

예를 들어, 다음과 같은 두 가지 동전의 배치를 생각하자.

첫 번째 배치에서 두 번째 배치로 만들기 위해서는 아래와 같이 최소 네 개의 동전을 옮겨야 한다.

현재 동전의 배치와 만들어야 하는 동전의 배치가 주어질 때, 옮겨야 하는 동전의 개수는 최소 몇 개인지 구하시오.

첫 번째 줄에 정수 $H\_1$, $W\_1$이 주어진다. ($1\le H\_1,W\_1\le 10$)

그다음 줄부터 $H\_1$개의 줄에 길이 $W\_1$의 문자열이 주어진다. ‘.’은 빈칸, ‘O’는 동전이 있는 칸이다. 현재 동전의 배치를 나타낸다.

그다음 줄에 정수 $H\_2$, $W\_2$가 주어진다. ($1\le H\_2,W\_2\le 10$)

그다음 줄부터 $H\_2$개의 줄에 길이 $W\_2$의 문자열이 주어진다. ‘.’은 빈칸, ‘O’는 동전이 있는 칸이다. 만들어야 하는 동전의 배치를 나타낸다.

두 배치의 동전의 개수는 동일함이 보장된다.

옮겨야 하는 동전의 최소 개수를 출력한다.