벽의 가치

Albert는 혼자서도 할 수 있는 보드 게임을 즐겨 한다. 이 게임을 하려면 먼저 $R$ 행 $C$ 열 크기의 격자 보드를 준비하고, 임의의 칸에 벽을 설치한다. 그다음 벽이 없는 빈칸 $N$개에 게임말을 하나씩 놓고, 남은 빈칸 중 한 곳을 골라 각 게임말이 도달해야 하는 목적지로 정한다. 목적지 칸의 위치를 $(r, c)$라 하자 ($r$ 행 $c$ 열). 편의상 게임말에는 1번부터 $N$번까지 번호가 붙어 있고, $i$번째 말이 놓인 칸을 $(X_i, Y_i)$라 하자.

예를 들어 아래 그림의 왼쪽은 $R = C = 4$인 보드를 나타내며, 'W'로 표시된 칸은 벽이고 '.'로 표시된 칸은 빈칸이다. 문자열 $A_i$를 보드의 $i$번째 행을 나타내는 길이 $C$의 문자열이라 하면, 이 보드는 $A = [".WW.", "..W.", ".WW.", "...."]$로 나타낼 수 있다. 오른쪽 그림은 Albert가 게임말 3개를 놓은 칸과 목적지를 나타내며, $X = [1, 1, 4]$, $Y = [1, 4, 4]$, $(r, c) = (2, 2)$이다.

각 말은 벽이 없는 빈칸을 따라 상하좌우로 이동해 목적지에 도달한다. $i$번째 말이 목적지까지 이동해야 하는 최소 거리를 $d_i$라 하자. 위 예에서 $d_1 = 2$ (하, 우 순서로 이동), $d_2 = 9$, $d_3 = 6$이다. 모든 말이 이동해야 하는 최소 거리의 합을 $D = \sum_{1 \le i \le N} d_i$라 하고, 이를 게임의 점수로 삼는다. 이 예의 점수는 $2 + 9 + 6 = 17$점이다.

Albert는 이 게임이 너무 심심하다고 느껴 조금 바꿔 보기로 했다. 먼저 처음의 보드 상태는 그대로 두고 벽을 하나 없앤다. 벽을 없애면 새 길이 생길 수 있으므로 점수는 같거나 낮아진다. 이 점수 차이를 없어진 벽의 가치라고 정의하자. 위 예에서는 벽이 5칸 있으므로, 아래 그림처럼 5가지 방법으로 벽을 하나 없앨 수 있다. 그림의 'X'는 벽을 없앤 칸을 표시한 것이며, 이제 빈칸이므로 게임말이 지나갈 수 있다.

이 다섯 가지 새 보드에서 점수를 구한 뒤 기존 점수 17점과의 차이를 구하면 없앤 벽의 가치가 된다. 왼쪽부터 차례로 구하면 다음과 같다.

• 가장 왼쪽 게임의 점수는 17점으로 기존 점수와 같으므로, (1, 2) 칸의 벽의 가치는 0이다.
• 왼쪽에서 두 번째 게임의 점수도 17점이고, (1, 3) 칸의 벽의 가치는 0이다.
• 왼쪽에서 세 번째 게임의 점수는 9점이다. 2번, 3번 말의 최소 거리가 $d_2 = 3$, $d_3 = 4$로 줄어들기 때문이다. 따라서 (2, 3) 칸의 벽의 가치는 8이다.
• 왼쪽에서 네 번째 게임의 점수는 13점이다. 2번, 3번 말의 최소 거리가 $d_2 = 7$, $d_3 = 4$로 줄어들기 때문이다. 따라서 (3, 2) 칸의 벽의 가치는 4이다.
• 왼쪽에서 다섯 번째 게임의 점수는 17점이므로, (3, 3) 칸의 벽의 가치는 0점이다.

다섯 개 벽의 가치를 모두 더하면 $0 + 0 + 8 + 4 + 0 = 12$가 된다. 이를 벽의 가치 총합이라 하자.

보드 상태가 주어졌을 때 기존 게임의 점수 $D$와 모든 벽의 가치 총합을 구하라.

첫 줄에 테스트 케이스의 수 $T$가 주어진다.

각 테스트 케이스의 첫 줄에는 $R$, $C$, $N$, $r$, $c$가 공백으로 구분되어 주어진다. 다음 $N$줄에는 각각 두 정수가 공백으로 구분되어 주어지며, 순서대로 $i$번째 게임말의 위치 $X_i$, $Y_i$를 나타낸다. 다음 $R$줄에는 각각 공백 없이 길이 $C$의 문자열이 주어지며, 순서대로 $i$번째 행의 보드 상태 $A_i$를 나타낸다. 벽이 있는 칸은 'W', 없는 칸은 '.'로 주어진다.

각 테스트 케이스의 정답으로 두 정수를 공백으로 구분해 한 줄에 출력한다. 첫 번째 정수는 기존 게임의 점수 $D$이고, 두 번째 정수는 모든 벽의 가치 총합이다.

• $1 \le T \le 5$
• $2 \le R, C \le 200$
• $1 \le N \le 50$
• $1 \le r \le R$, $1 \le c \le C$
• $1 \le i \le N$인 모든 $i$에 대하여:
  • $1 \le X_i \le R$, $1 \le Y_i \le C$
• 각 테스트 케이스 안에서 게임말의 위치와 목적지의 위치는 모두 서로 다르다. 같은 칸에 게임말이 두 개 있거나, 게임말과 목적지가 같은 칸에 있는 경우는 없다.
• 게임말의 위치와 목적지의 위치는 벽이 없는 칸임이 보장된다.
• 벽을 하나도 부수지 않아도, 각 게임말이 상하좌우로 이동하며 빈칸만 지나 목적지에 도달할 수 있는 테스트 케이스만 입력으로 주어진다.
• 벽은 적어도 1개 주어진다.