그리드 게임

무한히 넓은 그리드가 단위 정사각형 칸으로 나누어져 있다. 각 칸은 살아있거나 죽어있다.

매초 모든 칸의 상태가 다음 규칙에 따라 동시에 바뀐다.

• 칸 $C$ 자신과 $C$에 변을 맞댄 네 칸, 이 다섯 칸 중 하나라도 살아있으면 1초 뒤 $C$는 살아있다.
• 그렇지 않으면 1초 뒤 $C$는 죽어있다.

처음 그리드의 상태가 주어졌을 때, $K$초가 지난 뒤 살아있는 칸이 모두 몇 개인지 구하는 프로그램을 작성하시오.

첫째 줄에 처음 상태가 주어지는 직사각형 영역의 행의 개수 $N$과 열의 개수 $M$이 주어진다. ($1 \le N, M \le 50$)

둘째 줄부터 $N$개의 줄에 이 영역의 처음 상태가 한 줄에 $M$글자씩 주어진다. 살아있는 칸은 o, 죽어있는 칸은 .이다. 영역 밖의 칸은 처음에 모두 죽어있다.

마지막 줄에 $K$가 주어진다. ($1 \le K \le 1500$)

첫째 줄에 $K$초가 지난 뒤 살아있는 칸의 개수를 출력한다.

처음 상태가 아래와 같고 $K = 3$인 경우를 보자.

oo
o.

3초가 지난 뒤의 모습은 아래와 같다.

...oo...
..oooo..
.oooooo.
oooooooo
ooooooo.
.ooooo..
..ooo...
...o....