Порятунок Ентерпрайза#6965

Порятунок Ентерпрайза

4 секунди

128 мегабайтів

Дуже легка

Зореліт Ентерпрайз оточений клінгонами! Знайдіть найшвидший шлях евакуації та виведіть його час.

На вхід подається прямокутна сітка, де кожна клітинка містить або Ентерпрайз, або військовий корабель клінгонів певного типу. Кожен тип кораблів клінгонів має асоційований час, за який Ентерпрайз може його перемогти. Для порятунку Ентерпрайз повинен перемогти кожен корабель клінгонів на певному шляху до межі сітки. Клітинки вважаються сусідніми, якщо у них спільне ребро, але не кут (тобто чотири сусіди).

Вхідні дані

Перший рядок містить кількість тестів $t$ ( $2 \leq t \leq 100$ 2 \le t \le 100). Кожен тест починається з рядка, що містить три числа $k$ , $w$ і $h$ . Число $k$ ( $1 \leq k \leq 25$ 1 \le k \le 25) - кількість різних типів військових кораблів клінгонів. Число $w$ ( $2 \leq w \leq 1000$ 2 \le w \le 1000) - ширина сітки. Значення $h$ ( $1 \leq h \leq 1000$ 1 \le h \le 1000) - висота сітки.

Кожен з наступних $k$ рядків містить велику латинську літеру - тип корабля клінгонів і час, необхідний Ентерпрайзу, щоб перемогти його. Тип корабля не може бути "E". Час задається в хвилинах і лежить між $0$ і $100000$ включно. Усі рядки містять різні типи.

Кожен з наступних $h$ рядків містить $w$ великих літер (без пробілів між ними). Серед усіх $h$ рядків присутня лише одна літера "E", що вказує на місцезнаходження Ентерпрайза; всі інші великі літери - одні з $k$ перелічених вище, що вказують на тип військового корабля клінгонів у заданій точці.

Вихідні дані

Виведіть одне ціле число - час, достатній для порятунку корабля.

Приклади

Приклад 1