시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
10 초 128 MB 266 60 43 29.452%

문제

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

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

출력

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

예제 입력 1

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

예제 출력 1

2
400
W3sicHJvYmxlbV9pZCI6Ijk1MDUiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWM1ZDRcdWQxMzBcdWQ1MDRcdWI3N2NcdWM3NzRcdWM5ODhcdWQ2MzggXHVkMGM4XHVjZDljIiwiZGVzY3JpcHRpb24iOiI8cD5cdWM1ZDRcdWQxMzBcdWQ1MDRcdWI3N2NcdWM3NzRcdWM5ODhcdWQ2MzhcdWFjMDAgXHVkMDc0XHViOWMxXHVjNjI4XHVjNWQwXHVhYzhjIFx1ZDNlY1x1YzcwNFx1YjQxOFx1YzVjOFx1YjJlNCEgXHVhYzAwXHVjN2E1IFx1YmU2MFx1Yjk3OCBcdWMyZGNcdWFjMDQgXHViMGI0XHVjNWQwIFx1YjA5OFx1YWMwOCBcdWMyMTggXHVjNzg4XHViMjk0IFx1ZDBjOFx1Y2Q5YyBcdWI4ZThcdWQyYjhcdWI5N2MgXHVjYzNlXHVhY2UwIFx1YWRmOCBcdWMyZGNcdWFjMDRcdWM3NDQgXHVjZDljXHViODI1XHVkNTU4XHViNzdjLjxcL3A+XHJcblxyXG48cD5cdWM5YzFcdWMwYWNcdWFjMDFcdWQ2MTVcdWM3NTggXHVkM2M5XHViYTc0XHVjNzc0IFx1Yzc4NVx1YjgyNVx1YzczY1x1Yjg1YyBcdWM4ZmNcdWM1YjRcdWM5YzBcdWJhNzAsIFx1Yzc3NFx1YjI5NCBcdWM1ZDRcdWQxMzBcdWQ1MDRcdWI3N2NcdWM3NzRcdWM5ODhcdWQ2MzhcdWM2NDAgXHVkMDc0XHViOWMxXHVjNjI4IFx1YzgwNFx1ZDIyY1x1YzEyMFx1YjRlNFx1Yzc1OCBcdWM3MDRcdWNlNThcdWI0ZTRcdWM3NDQgXHVjNzU4XHViYmY4XHVkNTVjXHViMmU0LiBcdWQwNzRcdWI5YzFcdWM2MjggXHVjODA0XHVkMjJjXHVjMTIwXHVjNzQwIFx1YmE4NyBcdWFjMDBcdWM5YzBcdWM3NTggXHVkMDc0XHViNzk4XHVjMmE0XHViODVjIFx1YjA5OFx1YjIwNFx1YzViNFx1YzljMFx1YmE3MCwgXHVhYzAxIFx1ZDA3NFx1Yjc5OFx1YzJhNFx1Yzc1OCBcdWQwNzRcdWI5YzFcdWM2MjggXHVjODA0XHVkMjJjXHVjMTIwXHVjNzQ0IFx1YzVkNFx1ZDEzMFx1ZDUwNFx1Yjc3Y1x1Yzc3NFx1Yzk4OFx1ZDYzOFx1YWMwMCBcdWJiMzRcdWI4MjVcdWQ2NTQgXHVjMmRjXHVkMGE0XHViMjk0IFx1YjM3MFx1YzVkMCBcdWFjNzhcdWI5YWNcdWIyOTQgXHVjMmRjXHVhYzA0XHViM2M0IFx1Yzc4NVx1YjgyNVx1YzczY1x1Yjg1YyBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YzVkNFx1ZDEzMFx1ZDUwNFx1Yjc3Y1x1Yzc3NFx1Yzk4OFx1ZDYzOFx1YjI5NCBcdWQwYzhcdWNkOWNcdWQ1NThcdWIyOTQgXHVhY2JkXHViODVjXHVjNWQwIFx1Yzc4OFx1YjI5NCBcdWJhYThcdWI0ZTAgXHVkMDc0XHViOWMxXHVjNjI4IFx1YzgwNFx1ZDIyY1x1YzEyMFx1Yzc0NCBcdWJiMzRcdWI4MjVcdWQ2NTQgXHVjMmRjXHVkMGE0XHViYTcwIFx1Yzc4NVx1YjgyNVx1YjQxYyBcdWQzYzlcdWJhNzRcdWM3NTggXHVhYzAwXHVjN2E1XHVjNzkwXHViOWFjXHViODVjIFx1ZDBjOFx1Y2Q5Y1x1ZDU1Y1x1YjJlNC4gXHVjNzg1XHViODI1XHViNDFjIFx1ZDNjOVx1YmE3NFx1Yzc1OCBcdWIyZThcdWM3MDQgXHVjMGFjXHVhYzAxXHVkNjE1XHVjNzQwIFx1YWYyZFx1YzlkM1x1YzgxMFx1Yzc3NCBcdWM1NDRcdWIyY2MgXHVhYzAwXHVjN2E1XHVjNzkwXHViOWFjXHViODVjXHViOWNjIFx1YzVmMFx1YWNiMFx1YjQxY1x1YjJlNC4gKFx1Yzk4OSwgXHVhYzAxIFx1YjJlOFx1YzcwNCBcdWMwYWNcdWFjMDFcdWQ2MTVcdWM3NDAgNFx1YWMxY1x1Yzc1OCBcdWM3NzRcdWM2YzMgXHViMmU4XHVjNzA0IFx1YzBhY1x1YWMwMVx1ZDYxNVx1Yzc0NCBcdWFjMTZcdWIyOTRcdWIyZTQuKTxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCA8c3Ryb25nPlx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM3NTggXHVhYzFjXHVjMjE4IFQ8XC9zdHJvbmc+ICgyICZsZTsgVCAmbGU7IDEwMClcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWFjMDEgXHVjZjAwXHVjNzc0XHVjMmE0XHViMjk0IFx1Y2NhYiBcdWM5MDRcdWM1ZDAgXHVjMTM4XHVhYzFjXHVjNzU4IFx1YzIyYlx1Yzc5MCA8c3Ryb25nPkssIFcsIEg8XC9zdHJvbmc+XHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC48XC9wPlxyXG5cclxuPHA+PHN0cm9uZz5LPFwvc3Ryb25nPiZuYnNwOygxICZsZTsgSyAmbGU7IDI1KVx1YjI5NCA8c3Ryb25nPlx1ZDA3NFx1YjljMVx1YzYyOCBcdWM4MDRcdWQyMmNcdWMxMjBcdWM3NTggXHVkMDc0XHViNzk4XHVjMmE0IFx1YWMxY1x1YzIxODxcL3N0cm9uZz5cdWI5N2MgXHVjNzU4XHViYmY4XHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD48c3Ryb25nPlc8XC9zdHJvbmc+Jm5ic3A7KDEgJmxlOyBXICZsZTsgMTAwMClcdWIyOTQgPHN0cm9uZz5cdWQzYzlcdWJhNzRcdWM3NTggXHVkM2VkPFwvc3Ryb25nPlx1Yzc0NCBcdWM3NThcdWJiZjhcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPjxzdHJvbmc+SDxcL3N0cm9uZz4mbmJzcDsoMSAmbGU7IEggJmxlOyAxMDAwKVx1YjI5NCA8c3Ryb25nPlx1ZDNjOVx1YmE3NFx1Yzc1OCBcdWIxOTJcdWM3NzQ8XC9zdHJvbmc+XHViOTdjIFx1Yzc1OFx1YmJmOFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+Jm5ic3A7PFwvcD5cclxuXHJcbjxwPlx1YjJlNFx1Yzc0YyA8c3Ryb25nPksgXHVjOTA0PFwvc3Ryb25nPlx1YzVkMFx1YjI5NCA8c3Ryb25nPlx1ZDA3NFx1YjljMVx1YzYyOCBcdWM4MDRcdWQyMmNcdWMxMjBcdWM3NTggXHVkMDc0XHViNzk4XHVjMmE0IFx1Yzc3NFx1Yjk4NDxcL3N0cm9uZz5cdWFjZmMgPHN0cm9uZz5cdWJiMzRcdWI4MjVcdWQ2NTRcdWMyZGNcdWQwYTRcdWIyOTQgXHViMzcwXHVjNWQwIFx1YWM3OFx1YjlhY1x1YjI5NCBcdWMyZGNcdWFjMDQ8XC9zdHJvbmc+XHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC48XC9wPlxyXG5cclxuPHA+PHN0cm9uZz5cdWQwNzRcdWI5YzFcdWM2MjggXHVjODA0XHVkMjJjXHVjMTIwXHVjNzU4IFx1ZDA3NFx1Yjc5OFx1YzJhNCBcdWM3NzRcdWI5ODQ8XC9zdHJvbmc+XHVjNzQwIFx1YzU0Y1x1ZDMwY1x1YmNiMyBcdWIzMDBcdWJiMzhcdWM3OTBcdWI4NWMgXHVjOGZjXHVjNWI0XHVjOWMwXHViYTcwLCAmcXVvdDtFJnF1b3Q7IFx1YWMwMFx1YjQyMCBcdWMyMTggXHVjNWM2XHViMmU0LiBcdWQwNzRcdWI3OThcdWMyYTRcdWM3NTggXHVjNzc0XHViOTg0XHVjNzQwIFx1YWNiOVx1Y2U2MCBcdWMyMTggXHVjNWM2XHViMmU0LjxcL3A+XHJcblxyXG48cD48c3Ryb25nPlx1YmIzNFx1YjgyNVx1ZDY1NFx1YzJkY1x1ZDBhNFx1YjI5NCBcdWIzNzBcdWM1ZDAgXHVhYzc4XHViOWFjXHViMjk0IFx1YzJkY1x1YWMwNDxcL3N0cm9uZz5cdWM3NDAgJiMzOTtcdWJkODQmIzM5O1x1Yzc0NCBcdWIwOThcdWQwYzBcdWIwYjRcdWJhNzAgMCBcdWM3NzRcdWMwYzEsIDEwMCwwMDAgXHVjNzc0XHVkNTU4XHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWIyZTRcdWM3NGMgPHN0cm9uZz5IIFx1YzkwNDxcL3N0cm9uZz5cdWM1ZDBcdWIyOTQgPHN0cm9uZz5XIFx1YWMxYzxcL3N0cm9uZz5cdWM3NTggXHVjNTRjXHVkMzBjXHViY2IzIFx1YjMwMFx1YmIzOFx1Yzc5MFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIChcdWFjMDEgXHViYjM4XHVjNzkwIFx1YzBhY1x1Yzc3NFx1YzVkMFx1YjI5NCBcdWFjZjVcdWJjMzFcdWM3NzQgXHVjNWM2XHViMmU0Lik8XC9wPlxyXG5cclxuPHA+SCBcdWM5MDRcdWM3NTggVyBcdWFjMWMgXHViYjM4XHVjNzkwIFx1YzkxMSw8XC9wPlxyXG5cclxuPHA+PHN0cm9uZz4mcXVvdDtFJnF1b3Q7PFwvc3Ryb25nPlx1YjI5NCA8c3Ryb25nPlx1YzVkNFx1ZDEzMFx1ZDUwNFx1Yjc3Y1x1Yzc3NFx1Yzk4OFx1ZDYzOFx1Yzc1OCBcdWM3MDRcdWNlNTg8XC9zdHJvbmc+XHViOTdjIFx1Yzc1OFx1YmJmOFx1ZDU1OFx1YmE3MCwgPHN0cm9uZz5cdWJjMThcdWI0ZGNcdWMyZGMgXHVkNTU4XHViMDk4XHViOWNjIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC48XC9zdHJvbmc+PFwvcD5cclxuXHJcbjxwPiZxdW90O0UmcXVvdDtcdWFjMDAgXHVjNTQ0XHViMmNjJm5ic3A7PHN0cm9uZz5cdWIyZTRcdWI5NzggXHViYWE4XHViNGUwIFx1YmIzOFx1Yzc5MDxcL3N0cm9uZz5cdWIyOTQgPHN0cm9uZz5cdWQ1NzRcdWIyZjkgXHViMmU4XHVjNzA0IFx1ZDNjOVx1YmE3NFx1YzVkMCBcdWM3MDRcdWNlNThcdWQ1NWMmbmJzcDs8XC9zdHJvbmc+PHN0cm9uZz5cdWQwNzRcdWI5YzFcdWM2Mjg8XC9zdHJvbmc+PHN0cm9uZz4gXHVjODA0XHVkMjJjXHVjMTIwPFwvc3Ryb25nPlx1Yzc1ODxzdHJvbmc+IFx1ZDA3NFx1Yjc5OFx1YzJhNDxcL3N0cm9uZz5cdWM3NzRcdWFjZTAsIFx1YmMxOFx1YjRkY1x1YzJkYyBcdWM3MDQgSyBcdWM5MDRcdWM1ZDBcdWMxMWMgXHViYjM0XHViODI1XHVkNjU0XHVjMmRjXHVkMGE0XHViMjk0IFx1YjM3MFx1YzVkMCBcdWFjNzhcdWI5YWNcdWIyOTQgXHVjMmRjXHVhYzA0XHVhY2ZjIFx1ZDU2OFx1YWVkOCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVjNWQ0XHVkMTMwXHVkNTA0XHViNzdjXHVjNzc0XHVjOTg4XHVkNjM4XHVhYzAwIFx1ZDBjOFx1Y2Q5Y1x1ZDU1OFx1YjI5NCBcdWIzNzBcdWM1ZDAgXHVhYzc4XHViOWFjXHViMjk0IFx1Y2Q1Y1x1YzE4YyBcdWMyZGNcdWFjMDRcdWM3NDQgXHVjODE1XHVjMjE4XHViODVjIFx1Y2Q5Y1x1YjgyNVx1ZDU1OFx1Yjc3Yy48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiI5NTA1IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiRW50ZXJwcmlzaW5nIEVzY2FwZSIsImRlc2NyaXB0aW9uIjoiPHA+VGhlIEVudGVycHJpc2UgaXMgc3Vycm91bmRlZCBieSBLbGluZ29ucyEgRmluZCB0aGUgZXNjYXBlIHJvdXRlIHRoYXQgaGFzIHRoZSBxdWlja2VzdCBleGl0IHRpbWUsIGFuZCBwcmludCB0aGF0IHRpbWUuPFwvcD5cclxuXHJcbjxwPklucHV0IGlzIGEgcmVjdGFuZ3VsYXIgZ3JpZDsgZWFjaCBncmlkIHNxdWFyZSBlaXRoZXIgaGFzIHRoZSBFbnRlcnByaXNlIG9yIHNvbWUgY2xhc3Mgb2YgYSBLbGluZ29uIHdhcnNoaXAuIEFzc29jaWF0ZWQgd2l0aCBlYWNoIGNsYXNzIG9mIEtsaW5nb24gd2Fyc2hpcCBpcyBhIHRpbWUgdGhhdCBpdCB0YWtlcyBmb3IgdGhlIEVudGVycHJpc2UgdG8gZGVmZWF0IHRoYXQgS2xpbmdvbi4gVG8gZXNjYXBlLCB0aGUgRW50ZXJwcmlzZSBtdXN0IGRlZmVhdCBlYWNoIEtsaW5nb24gb24gc29tZSBwYXRoIHRvIHRoZSBwZXJpbWV0ZXIuIFNxdWFyZXMgYXJlIGNvbm5lY3RlZCBieSB0aGVpciBlZGdlcywgbm90IGJ5IGNvcm5lcnMgKHRodXMsIGZvdXIgbmVpZ2hib3JzKS48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBmaXJzdCBsaW5lIHdpbGwgY29udGFpbiBULCB0aGUgbnVtYmVyIG9mIGNhc2VzOyAyICZsZTsgVCAmbGU7IDEwMC4gRWFjaCBjYXNlIHdpbGwgc3RhcnQgd2l0aCBsaW5lIGNvbnRhaW5pbmcgdGhyZWUgbnVtYmVycyBrLCB3LCBhbmQgaC4gVGhlIHZhbHVlIGZvciBrIGlzIHRoZSBudW1iZXIgb2YgZGlmZmVyZW50IEtsaW5nb24gY2xhc3NlcyBhbmQgd2lsbCBiZSBiZXR3ZWVuIDEgYW5kIDI1LCBpbmNsdXNpdmUuIFRoZSB2YWx1ZSBmb3IgdyBpcyB0aGUgd2lkdGggb2YgdGhlIGdyaWQgYW5kIHdpbGwgYmUgYmV0d2VlbiAxIGFuZCAxMDAwLCBpbmNsdXNpdmUuIFRoZSB2YWx1ZSBmb3IgaCBpcyB0aGUgaGVpZ2h0IG9mIHRoZSBncmlkIGFuZCB3aWxsIGJlIGJldHdlZW4gMSBhbmQgMTAwMCwgaW5jbHVzaXZlLjxcL3A+XHJcblxyXG48cD5Gb2xsb3dpbmcgdGhhdCB3aWxsIGJlIGsgbGluZXMuIEVhY2ggd2lsbCBjb25zaXN0IG9mIGEgY2FwaXRhbCBsZXR0ZXIgdXNlZCB0byBsYWJlbCB0aGUgY2xhc3Mgb2YgS2xpbmdvbiBzaGlwcyBmb2xsb3dlZCBieSB0aGUgZHVyYXRpb24gcmVxdWlyZWQgdG8gZGVmZWF0IHRoYXQgY2xhc3Mgb2YgS2xpbmdvbi4gVGhlIGxhYmVsIHdpbGwgbm90IGJlICZsZHF1bztFJnJkcXVvOy4gVGhlIGR1cmF0aW9uIGlzIGluIG1pbnV0ZXMgYW5kIHdpbGwgYmUgYmV0d2VlbiAwIGFuZCAxMDAsMDAwLCBpbmNsdXNpdmUuIEVhY2ggbGFiZWwgd2lsbCBiZSBkaXN0aW5jdC48XC9wPlxyXG5cclxuPHA+Rm9sbG93aW5nIHRoYXQgd2lsbCBiZSBoIGxpbmVzLiBFYWNoIHdpbGwgY29uc2lzdCBvZiB3IGNhcGl0YWwgbGV0dGVycyAod2l0aCBubyBzcGFjZXMgYmV0d2VlbiB0aGVtKS4gVGhlcmUgd2lsbCBiZSBleGFjdGx5IG9uZSAmbGRxdW87RSZyZHF1bzsgYWNyb3NzIGFsbCBoIGxpbmVzLCBkZW5vdGluZyB0aGUgbG9jYXRpb24gb2YgdGhlIEVudGVycHJpc2U7IGFsbCBvdGhlciBjYXBpdGFsIGxldHRlcnMgd2lsbCBiZSBvbmUgb2YgdGhlIGsgbGFiZWxzIGdpdmVuIGFib3ZlLCBkZW5vdGluZyB0aGUgY2xhc3Mgb2YgS2xpbmdvbiB3YXJzaGlwIGluIHRoZSBzcXVhcmUuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+WW91ciBvdXRwdXQgc2hvdWxkIGJlIGEgc2luZ2xlIGludGVnZXIgdmFsdWUgaW5kaWNhdGluZyB0aGUgdGltZSByZXF1aXJlZCBmb3IgdGhlIEVudGVycHJpc2UgdG8gZXNjYXBlLjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==