Ключи
Миссия Джона состоит в том, чтобы украсть некоторые важные документы с одноэтажного здания. Он сумел достать подробный план этажа здания, с указанием расположения всех документов. В здании имеются двери, для открытия которых требуются ключи. У Джона имеется несколько ключей. Некоторые ключи расположены и в самом здании.
Помогите Джону выяснить, сколько документов он может украсть.
Входные данные
Первая строка состоит из нескольких тестов, не более 100. Каждый тест состоит из:
одна строка с двумя целыми числами h и w (2 ≤ h, w ≤ 100): высота и ширина карты.
h строк по w символов, описывающих карту:
'.' - пустое место.
'*' - непроходимая стена.
'$' - документ, который Джон хочет украсть.
буква верхнего регистра - дверь.
буква нижнего регистра - ключ, открывающий дверь с соответствующей буквой верхнего регистра.
одна строка из различных букв нижнего регистра: ключи, имеющиеся у Джона. Если у него ключей нет, то строка содержит "0".
Джон может свободно передвигаться с внешней стороне здания. Для любой двери количество ключей, которые ее открывают, может равняться нулю, одному, или быть больше одного. Для любого ключа количество дверей, которые он открывает, может равняться нулю, одному, или быть больше одного. Ключи могут быть использованы повторно.
Выходные данные
Для каждого теста вывести в отдельной строке общее количество документов, которое сможет украсть Джон.