Порятунок Ентерпрайза
Зореліт Ентерпрайз оточений клінгонами! Знайдіть найшвидший шлях евакуації та виведіть його час.
На вхід подається прямокутна сітка, де кожна клітинка містить або Ентерпрайз, або військовий корабель клінгонів певного типу. Кожен тип кораблів клінгонів має асоційований час, за який Ентерпрайз може його перемогти. Для порятунку Ентерпрайз повинен перемогти кожен корабель клінгонів на певному шляху до межі сітки. Клітинки вважаються сусідніми, якщо у них спільне ребро, але не кут (тобто чотири сусіди).
Вхідні дані
Перший рядок містить кількість тестів t (2 ≤ t ≤ 100). Кожен тест починається з рядка, що містить три числа k, w і h. Число k (1 ≤ k ≤ 25) - кількість різних типів військових кораблів клінгонів. Число w (2 ≤ w ≤ 1000) - ширина сітки. Значення h (1 ≤ h ≤ 1000) - висота сітки.
Кожна з наступних k рядків містить велику латинську літеру - тип корабля клінгонів і час, необхідний Ентерпрайзу, щоб перемогти його. Тип корабля не може бути "E". Час задається в хвилинах і лежить між 0 і 100000 включно. Усі рядки містять різні типи.
Кожна з наступних h рядків містить w великих літер (без пробілів між ними). Серед усіх h рядків присутня лише одна літера "E", що вказує на місцезнаходження Ентерпрайза; всі інші великі літери - одні з k перелічених вище, що вказують на тип військового корабля клінгонів у заданій точці.
Вихідні дані
Виведіть одне ціле число - час, достатній для порятунку корабля.