엔터프라이즈호 탈출

엔터프라이즈호가 클링온 함대에 포위되었다. 가장 빨리 빠져나갈 수 있는 탈출 경로를 찾아 걸리는 시간을 구하라.

직사각형 격자가 주어진다. 각 칸에는 엔터프라이즈호가 있거나 클링온 전투선이 한 척 있다. 클링온 전투선은 여러 클래스로 나뉘고, 클래스마다 엔터프라이즈호가 그 전투선을 무력화하는 데 걸리는 시간이 정해져 있다.

엔터프라이즈호는 변을 맞댄 이웃 칸으로만 움직인다. 즉 한 칸의 이웃은 최대 네 개이고, 꼭짓점만 닿은 칸으로는 갈 수 없다. 새로 들어가는 칸마다 그 칸의 전투선을 무력화해야 하며 그만큼 시간이 걸린다. 출발한 칸에서는 시간이 들지 않는다.

격자의 첫 줄, 마지막 줄, 첫 열, 마지막 열에 있는 칸을 가장자리 칸이라 하자. 엔터프라이즈호는 가장자리 칸에 도착해 그 칸의 전투선을 무력화하면 추가 시간 없이 격자 밖으로 빠져나간다. 처음부터 가장자리 칸에 있으면 곧바로 탈출하므로 걸리는 시간은 0이다.

첫째 줄에 테스트 케이스의 개수 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개가 공백 없이 주어진다. "E"는 엔터프라이즈호의 위치이고 격자 전체에 정확히 하나 있다. 나머지 문자는 그 칸에 있는 클링온 전투선의 클래스이며, 앞의 K개 줄에 반드시 나온다.

각 테스트 케이스마다 엔터프라이즈호가 탈출하는 데 걸리는 최소 시간을 정수로 한 줄에 출력하라.