시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
10 초 128 MB 262 57 41 28.671%

문제

엔터프라이즈호가 클링온에게 포위되었다! 가장 빠른 시간 내에 나갈 수 있는 탈출 루트를 찾고 그 시간을 출력하라.

직사각형의 평면이 입력으로 주어지며, 이는 엔터프라이즈호와 클링온 전투선들의 위치들을 의미한다. 클링온 전투선은 몇 가지의 클래스로 나누어지며, 각 클래스의 클링온 전투선을 엔터프라이즈호가 무력화 시키는 데에 걸리는 시간도 입력으로 주어진다. 엔터프라이즈호는 탈출하는 경로에 있는 모든 클링온 전투선을 무력화 시키며 입력된 평면의 가장자리로 탈출한다. 입력된 평면의 단위 사각형은 꼭짓점이 아닌 가장자리로만 연결된다. (즉, 각 단위 사각형은 4개의 이웃 단위 사각형을 갖는다.)

입력

첫째줄에 테스트 케이스의 갯수 T (2 ≤ T ≤ 100)가 주어진다.

각 케이스는 첫 줄에 세개의 숫자 K, W, H가 주어진다.

K (1 ≤ K ≤ 25)는 클링온 전투선의 클래스 갯수를 의미한다.

W (1 ≤ W ≤ 1000)는 평면의 폭을 의미한다.

H (1 ≤ H ≤ 1000)는 평면의 높이를 의미한다.

 

다음 K 줄에는 클링온 전투선의 클래스 이름무력화시키는 데에 걸리는 시간이 주어진다.

클링온 전투선의 클래스 이름은 알파벳 대문자로 주어지며, "E" 가될 수 없다. 클래스의 이름은 겹칠 수 없다.

무력화시키는 데에 걸리는 시간은 '분'을 나타내며 0 이상, 100,000 이하이다.

다음 H 줄에는 W 개의 알파벳 대문자가 주어진다. (각 문자 사이에는 공백이 없다.)

H 줄의 W 개 문자 중,

"E"엔터프라이즈호의 위치를 의미하며, 반드시 하나만 주어진다.

"E"가 아닌 다른 모든 문자해당 단위 평면에 위치한 클링온 전투선 클래스이고, 반드시 위 K 줄에서 무력화시키는 데에 걸리는 시간과 함께 주어진다.

출력

엔터프라이즈호가 탈출하는 데에 걸리는 최소 시간을 정수로 출력하라.

예제 입력

2
6 3 3
A 1
B 2
C 3
D 4
F 5
G 6
ABC
FEC
DBG
2 6 3
A 100
B 1000
BBBBBB
AAAAEB
BBBBBB

예제 출력

2
400

힌트