도쿄 올림픽 센터

당신은 프로그래밍 대회 여름 합숙 훈련에 참가하고 있다. 합숙은 도쿄 올림픽 센터라는 숙박 시설에서 열리며, 오늘이 마지막 날이다. 하필 당신이 참가자 전원의 방 청소 상태를 점검하는 일을 맡았다.

시설은 높이가 $H$, 너비가 $W$인 직사각형 구역이고, 정사각형 칸으로 나뉘어 있다. 행은 위에서 아래로 $1$번부터 $H$번까지, 열은 왼쪽에서 오른쪽으로 $1$번부터 $W$번까지 번호를 붙인다. $i$행 $j$열의 칸을 $(i, j)$로 쓴다. 두 칸이 변을 맞대고 있으면 두 칸은 서로 인접하다.

각 칸은 벽 칸이거나 바닥 칸이다. 벽 칸에는 아무도 들어갈 수 없다. 바닥 칸은 시설의 내부이고, 인접한 두 바닥 칸 사이는 누구나 이동할 수 있다. 바닥 칸은 여러 구역으로 나뉘고, 각 구역에는 알파벳 대문자 이름이 하나씩 붙는다(A, B, C, ...). 인접한 바닥 칸이 정확히 하나뿐인 바닥 칸을 방이라고 하고, 그렇지 않은 바닥 칸을 복도라고 한다.

다음 그림은 시설 하나를 나타낸 것이다. 벽 칸은 마침표 하나로 표시한다.

...................
.....AAABBBBBBB....
...A.AA.A...B.B..B.
..AAAAAAAABBBBBBBB.
...A..A.A.....B....
......A.......BBBB.
....A.AA..C.C...B..
...AAAAACCCCCCBBBB.
...A..A...C.C...B..
...................

이 그림에서 구역 A의 방은 $7$개, 구역 B의 방은 $4$개, 구역 C의 방은 $4$개다.

시설이 너무 넓어 혼자 다 돌 수는 없으므로, 당신은 합숙에 참가한 다른 사람에게 방 점검을 부탁했다. 이들을 직원이라고 부르자. 지금 칸 $(s, t)$에 직원 $K$명이 서 있고, 점검은 다음 순서로 진행한다.

1. 먼저 각 직원에게 구역을 배정한다. 모든 구역은 정확히 한 직원에게 배정해야 한다. 한 직원에게 모든 구역을 배정해도 되고, 어떤 직원에게는 구역을 하나도 배정하지 않아도 된다.
2. 그다음 모든 직원이 동시에 배정받은 구역의 방을 점검하기 시작한다. 인접한 두 바닥 칸 사이를 이동하는 데는 $T_{move}$의 시간이 걸린다. 칸 $(i, j)$의 방을 점검하려면 그 칸까지 이동한 뒤 그 자리에서 $T_{check}$의 시간을 써야 한다. 각 직원은 배정받은 구역을 어떤 순서로 점검할지 먼저 정하고, 정한 순서를 그대로 지킨다. 예를 들어 구역 A, C, E를 배정받은 직원은 순서를 E, A, C로 정할 수 있다. 그러면 구역 E의 방을 모두 점검한 뒤 구역 A의 방을 모두 점검하고, 마지막으로 구역 C의 방을 점검한다. 직원은 어느 바닥 칸이든 지나갈 수 있다. 그러나 배정받지 않은 구역의 방은 점검할 수 없고, 정한 구역 순서를 어겨 점검할 수도 없다.
3. 배정받은 방을 모두 점검한 직원은 칸 $(s, t)$로 돌아온다.
4. 모든 직원이 칸 $(s, t)$로 돌아오면 작업이 끝난다.

직원은 모두 같은 순간에 출발해 동시에 움직인다. 따라서 작업에 걸리는 시간은 직원 한 명이 쓴 시간 중 가장 큰 값이다. 다음 대회가 시작하기 전에 점검을 마쳐야 하므로, 이 시간을 최소로 만들어야 한다.

첫째 줄에 세 정수 $H$, $W$, $K$가 주어진다($1 \le H \le 50$, $1 \le W \le 50$, $1 \le K \le 12$). 둘째 줄에 네 정수 $s$, $t$, $T_{move}$, $T_{check}$가 주어진다($1 \le s \le H$, $1 \le t \le W$, $1 \le T_{move}, T_{check} \le 10000$).

이어지는 $H$개의 줄에는 각각 문자가 정확히 $W$개씩 주어져 시설의 칸을 나타낸다. 이 줄들 중 $i$번째 줄의 $j$번째 문자는 칸 $(i, j)$가 벽 칸이면 마침표 하나이고, 벽 칸이 아니면 칸 $(i, j)$가 속한 구역을 나타내는 A부터 L까지의 대문자다.

입력은 다음을 모두 만족한다.

• 각 구역의 방은 $1$개 이상 $12$개 이하다.
• 칸 $(s, t)$는 복도다.
• 한 구역에 속한 바닥 칸은 서로 연결되어 있다.
• 시설의 모든 바닥 칸은 서로 연결되어 있다.
• 각 구역의 바닥 칸은 두 개 이상이다.

모든 방을 점검하는 데 필요한 최소 시간을 한 줄에 출력한다.