놀라운 미로

M행 N열의 칸으로 이루어진 미로가 있다. 각 칸에는 상하좌우 네 인접 칸으로 향하는 문이 있지만, 한 순간에는 정확히 한 방향의 문만 열려 있다. A에서 B로 나가는 문과 B에서 A로 나가는 문은 서로 독립적으로 작동한다.

각 칸에서 처음 열려 있는 방향은 입력으로 주어진다. 모든 문은 1분마다 N, E, S, W, N 순서로 시계 방향 90도씩 회전한다.

당신은 1분 동안 현재 칸에서 그 순간 열려 있는 방향으로 한 칸 이동할 수 있다. 또는 원하는 방향의 문이 열릴 때까지 그 자리에 머물러 1분을 기다릴 수 있다. 열린 문이 미로 밖을 향하면 그 1분에는 이동할 수 없지만 기다릴 수는 있다.

시작 위치는 (1, 1)이다. 목표는 K개의 보물상자를 모두 모은 뒤 (M, N)에 도착하는 것이다. 모든 보물상자를 모으기 전에 (M, N)에 갈 수는 있지만, 탈출은 보물을 전부 모은 상태로 (M, N)에 있을 때만 가능하다.

미로를 탈출하는 데 필요한 최소 시간을 구하시오.

입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 두 정수 M, N (2 <= M, N <= 100)으로 시작한다.

다음 M개의 줄에는 각 줄마다 N개의 문자가 주어진다. 각 문자는 N, E, S, W 중 하나이며, 해당 칸에서 처음 열려 있는 문의 방향을 뜻한다. 위치가 (r, c)인 칸에서 N, E, S, W는 각각 (r - 1, c), (r, c + 1), (r + 1, c), (r, c - 1) 방향을 의미한다.

그다음 보물상자의 개수 K (1 <= K <= 8)가 주어진다. 이어지는 K개의 줄에는 각 보물상자의 위치 R, C가 주어진다. 한 칸에 보물상자가 여러 개 있는 경우는 없으며, 보물상자가 (1, 1)이나 (M, N)에 놓이는 경우도 없다.

마지막 줄의 0 0은 입력의 끝을 나타낸다.

각 테스트 케이스마다 미로를 탈출하는 데 필요한 최소 시간을 출력한다.