시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
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+XHVjY2FiXHVjOWY4XHVjOTA0XHVjNWQwIDxzdHJvbmc+XHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1Yzc1OCBcdWFjMmZcdWMyMTggVDxcL3N0cm9uZz4gKDIgJmxlOyBUICZsZTsgMTAwKVx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YWMwMSBcdWNmMDBcdWM3NzRcdWMyYTRcdWIyOTQgXHVjY2FiIFx1YzkwNFx1YzVkMCBcdWMxMzhcdWFjMWNcdWM3NTggXHVjMjJiXHVjNzkwIDxzdHJvbmc+SywgVywgSDxcL3N0cm9uZz5cdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LjxcL3A+XHJcblxyXG48cD48c3Ryb25nPks8XC9zdHJvbmc+Jm5ic3A7KDEgJmxlOyBLICZsZTsgMjUpXHViMjk0IDxzdHJvbmc+XHVkMDc0XHViOWMxXHVjNjI4IFx1YzgwNFx1ZDIyY1x1YzEyMFx1Yzc1OCBcdWQwNzRcdWI3OThcdWMyYTQgXHVhYzJmXHVjMjE4PFwvc3Ryb25nPlx1Yjk3YyBcdWM3NThcdWJiZjhcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPjxzdHJvbmc+VzxcL3N0cm9uZz4mbmJzcDsoMSAmbGU7IFcgJmxlOyAxMDAwKVx1YjI5NCA8c3Ryb25nPlx1ZDNjOVx1YmE3NFx1Yzc1OCBcdWQzZWQ8XC9zdHJvbmc+XHVjNzQ0IFx1Yzc1OFx1YmJmOFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+PHN0cm9uZz5IPFwvc3Ryb25nPiZuYnNwOygxICZsZTsgSCAmbGU7IDEwMDApXHViMjk0IDxzdHJvbmc+XHVkM2M5XHViYTc0XHVjNzU4IFx1YjE5Mlx1Yzc3NDxcL3N0cm9uZz5cdWI5N2MgXHVjNzU4XHViYmY4XHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD4mbmJzcDs8XC9wPlxyXG5cclxuPHA+XHViMmU0XHVjNzRjIDxzdHJvbmc+SyBcdWM5MDQ8XC9zdHJvbmc+XHVjNWQwXHViMjk0IDxzdHJvbmc+XHVkMDc0XHViOWMxXHVjNjI4IFx1YzgwNFx1ZDIyY1x1YzEyMFx1Yzc1OCBcdWQwNzRcdWI3OThcdWMyYTQgXHVjNzc0XHViOTg0PFwvc3Ryb25nPlx1YWNmYyA8c3Ryb25nPlx1YmIzNFx1YjgyNVx1ZDY1NFx1YzJkY1x1ZDBhNFx1YjI5NCBcdWIzNzBcdWM1ZDAgXHVhYzc4XHViOWFjXHViMjk0IFx1YzJkY1x1YWMwNDxcL3N0cm9uZz5cdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LjxcL3A+XHJcblxyXG48cD48c3Ryb25nPlx1ZDA3NFx1YjljMVx1YzYyOCBcdWM4MDRcdWQyMmNcdWMxMjBcdWM3NTggXHVkMDc0XHViNzk4XHVjMmE0IFx1Yzc3NFx1Yjk4NDxcL3N0cm9uZz5cdWM3NDAgXHVjNTRjXHVkMzBjXHViY2IzIFx1YjMwMFx1YmIzOFx1Yzc5MFx1Yjg1YyBcdWM4ZmNcdWM1YjRcdWM5YzBcdWJhNzAsICZxdW90O0UmcXVvdDsgXHVhYzAwXHViNDIwIFx1YzIxOCBcdWM1YzZcdWIyZTQuIFx1ZDA3NFx1Yjc5OFx1YzJhNFx1Yzc1OCBcdWM3NzRcdWI5ODRcdWM3NDAgXHVhY2I5XHVjZTYwIFx1YzIxOCBcdWM1YzZcdWIyZTQuPFwvcD5cclxuXHJcbjxwPjxzdHJvbmc+XHViYjM0XHViODI1XHVkNjU0XHVjMmRjXHVkMGE0XHViMjk0IFx1YjM3MFx1YzVkMCBcdWFjNzhcdWI5YWNcdWIyOTQgXHVjMmRjXHVhYzA0PFwvc3Ryb25nPlx1Yzc0MCAmIzM5O1x1YmQ4NCYjMzk7XHVjNzQ0IFx1YjA5OFx1ZDBjMFx1YjBiNFx1YmE3MCAwIFx1Yzc3NFx1YzBjMSwgMTAwLDAwMCBcdWM3NzRcdWQ1NThcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YjJlNFx1Yzc0YyA8c3Ryb25nPkggXHVjOTA0PFwvc3Ryb25nPlx1YzVkMFx1YjI5NCA8c3Ryb25nPlcgXHVhYzFjPFwvc3Ryb25nPlx1Yzc1OCBcdWM1NGNcdWQzMGNcdWJjYjMgXHViMzAwXHViYjM4XHVjNzkwXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gKFx1YWMwMSBcdWJiMzhcdWM3OTAgXHVjMGFjXHVjNzc0XHVjNWQwXHViMjk0IFx1YWNmNVx1YmMzMVx1Yzc3NCBcdWM1YzZcdWIyZTQuKTxcL3A+XHJcblxyXG48cD5IIFx1YzkwNFx1Yzc1OCBXIFx1YWMxYyBcdWJiMzhcdWM3OTAgXHVjOTExLDxcL3A+XHJcblxyXG48cD48c3Ryb25nPiZxdW90O0UmcXVvdDs8XC9zdHJvbmc+XHViMjk0IDxzdHJvbmc+XHVjNWQ0XHVkMTMwXHVkNTA0XHViNzdjXHVjNzc0XHVjOTg4XHVkNjM4XHVjNzU4IFx1YzcwNFx1Y2U1ODxcL3N0cm9uZz5cdWI5N2MgXHVjNzU4XHViYmY4XHVkNTU4XHViYTcwLCA8c3Ryb25nPlx1YmMxOFx1YjRkY1x1YzJkYyBcdWQ1NThcdWIwOThcdWI5Y2MgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LjxcL3N0cm9uZz48XC9wPlxyXG5cclxuPHA+JnF1b3Q7RSZxdW90O1x1YWMwMCBcdWM1NDRcdWIyY2MmbmJzcDs8c3Ryb25nPlx1YjJlNFx1Yjk3OCBcdWJhYThcdWI0ZTAgXHViYjM4XHVjNzkwPFwvc3Ryb25nPlx1YjI5NCA8c3Ryb25nPlx1ZDU3NFx1YjJmOSBcdWIyZThcdWM3MDQgXHVkM2M5XHViYTc0XHVjNWQwIFx1YzcwNFx1Y2U1OFx1ZDU1YyZuYnNwOzxcL3N0cm9uZz48c3Ryb25nPlx1ZDA3NFx1YjljMVx1YzYyODxcL3N0cm9uZz48c3Ryb25nPiBcdWM4MDRcdWQyMmNcdWMxMjA8XC9zdHJvbmc+XHVjNzU4PHN0cm9uZz4gXHVkMDc0XHViNzk4XHVjMmE0PFwvc3Ryb25nPlx1Yzc3NFx1YWNlMCwgXHViYzE4XHViNGRjXHVjMmRjIFx1YzcwNCBLIFx1YzkwNFx1YzVkMFx1YzExYyBcdWJiMzRcdWI4MjVcdWQ2NTRcdWMyZGNcdWQwYTRcdWIyOTQgXHViMzcwXHVjNWQwIFx1YWM3OFx1YjlhY1x1YjI5NCBcdWMyZGNcdWFjMDRcdWFjZmMgXHVkNTY4XHVhZWQ4IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWM1ZDRcdWQxMzBcdWQ1MDRcdWI3N2NcdWM3NzRcdWM5ODhcdWQ2MzhcdWFjMDAgXHVkMGM4XHVjZDljXHVkNTU4XHViMjk0IFx1YjM3MFx1YzVkMCBcdWFjNzhcdWI5YWNcdWIyOTQgXHVjZDVjXHVjMThjIFx1YzJkY1x1YWMwNFx1Yzc0NCBcdWM4MTVcdWMyMThcdWI4NWMgXHVjZDljXHViODI1XHVkNTU4XHViNzdjLjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6Ijk1MDUiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJFbnRlcnByaXNpbmcgRXNjYXBlIiwiZGVzY3JpcHRpb24iOiI8cD5UaGUgRW50ZXJwcmlzZSBpcyBzdXJyb3VuZGVkIGJ5IEtsaW5nb25zISBGaW5kIHRoZSBlc2NhcGUgcm91dGUgdGhhdCBoYXMgdGhlIHF1aWNrZXN0IGV4aXQgdGltZSwgYW5kIHByaW50IHRoYXQgdGltZS48XC9wPlxyXG5cclxuPHA+SW5wdXQgaXMgYSByZWN0YW5ndWxhciBncmlkOyBlYWNoIGdyaWQgc3F1YXJlIGVpdGhlciBoYXMgdGhlIEVudGVycHJpc2Ugb3Igc29tZSBjbGFzcyBvZiBhIEtsaW5nb24gd2Fyc2hpcC4gQXNzb2NpYXRlZCB3aXRoIGVhY2ggY2xhc3Mgb2YgS2xpbmdvbiB3YXJzaGlwIGlzIGEgdGltZSB0aGF0IGl0IHRha2VzIGZvciB0aGUgRW50ZXJwcmlzZSB0byBkZWZlYXQgdGhhdCBLbGluZ29uLiBUbyBlc2NhcGUsIHRoZSBFbnRlcnByaXNlIG11c3QgZGVmZWF0IGVhY2ggS2xpbmdvbiBvbiBzb21lIHBhdGggdG8gdGhlIHBlcmltZXRlci4gU3F1YXJlcyBhcmUgY29ubmVjdGVkIGJ5IHRoZWlyIGVkZ2VzLCBub3QgYnkgY29ybmVycyAodGh1cywgZm91ciBuZWlnaGJvcnMpLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGZpcnN0IGxpbmUgd2lsbCBjb250YWluIFQsIHRoZSBudW1iZXIgb2YgY2FzZXM7IDIgJmxlOyBUICZsZTsgMTAwLiBFYWNoIGNhc2Ugd2lsbCBzdGFydCB3aXRoIGxpbmUgY29udGFpbmluZyB0aHJlZSBudW1iZXJzIGssIHcsIGFuZCBoLiBUaGUgdmFsdWUgZm9yIGsgaXMgdGhlIG51bWJlciBvZiBkaWZmZXJlbnQgS2xpbmdvbiBjbGFzc2VzIGFuZCB3aWxsIGJlIGJldHdlZW4gMSBhbmQgMjUsIGluY2x1c2l2ZS4gVGhlIHZhbHVlIGZvciB3IGlzIHRoZSB3aWR0aCBvZiB0aGUgZ3JpZCBhbmQgd2lsbCBiZSBiZXR3ZWVuIDEgYW5kIDEwMDAsIGluY2x1c2l2ZS4gVGhlIHZhbHVlIGZvciBoIGlzIHRoZSBoZWlnaHQgb2YgdGhlIGdyaWQgYW5kIHdpbGwgYmUgYmV0d2VlbiAxIGFuZCAxMDAwLCBpbmNsdXNpdmUuPFwvcD5cclxuXHJcbjxwPkZvbGxvd2luZyB0aGF0IHdpbGwgYmUgayBsaW5lcy4gRWFjaCB3aWxsIGNvbnNpc3Qgb2YgYSBjYXBpdGFsIGxldHRlciB1c2VkIHRvIGxhYmVsIHRoZSBjbGFzcyBvZiBLbGluZ29uIHNoaXBzIGZvbGxvd2VkIGJ5IHRoZSBkdXJhdGlvbiByZXF1aXJlZCB0byBkZWZlYXQgdGhhdCBjbGFzcyBvZiBLbGluZ29uLiBUaGUgbGFiZWwgd2lsbCBub3QgYmUgJmxkcXVvO0UmcmRxdW87LiBUaGUgZHVyYXRpb24gaXMgaW4gbWludXRlcyBhbmQgd2lsbCBiZSBiZXR3ZWVuIDAgYW5kIDEwMCwwMDAsIGluY2x1c2l2ZS4gRWFjaCBsYWJlbCB3aWxsIGJlIGRpc3RpbmN0LjxcL3A+XHJcblxyXG48cD5Gb2xsb3dpbmcgdGhhdCB3aWxsIGJlIGggbGluZXMuIEVhY2ggd2lsbCBjb25zaXN0IG9mIHcgY2FwaXRhbCBsZXR0ZXJzICh3aXRoIG5vIHNwYWNlcyBiZXR3ZWVuIHRoZW0pLiBUaGVyZSB3aWxsIGJlIGV4YWN0bHkgb25lICZsZHF1bztFJnJkcXVvOyBhY3Jvc3MgYWxsIGggbGluZXMsIGRlbm90aW5nIHRoZSBsb2NhdGlvbiBvZiB0aGUgRW50ZXJwcmlzZTsgYWxsIG90aGVyIGNhcGl0YWwgbGV0dGVycyB3aWxsIGJlIG9uZSBvZiB0aGUgayBsYWJlbHMgZ2l2ZW4gYWJvdmUsIGRlbm90aW5nIHRoZSBjbGFzcyBvZiBLbGluZ29uIHdhcnNoaXAgaW4gdGhlIHNxdWFyZS48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5Zb3VyIG91dHB1dCBzaG91bGQgYmUgYSBzaW5nbGUgaW50ZWdlciB2YWx1ZSBpbmRpY2F0aW5nIHRoZSB0aW1lIHJlcXVpcmVkIGZvciB0aGUgRW50ZXJwcmlzZSB0byBlc2NhcGUuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d