Звездолет Энтерпрайз окружен Клингонами! Найдите самый быстрый путь эвакуации и выведите его время.

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

Входные данные

Первая строка содержит количество тестов 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 перечисленных выше, указывающих на тип военного корабля Клингонов в заданной точке.

Выходные данные

Выведите одно целое число - время, достаточное для спасения корабля.