Задачі
Ключи
Ключи
Миссия Джона состоит в том, чтобы украсть некоторые важные документы с одноэтажного здания. Он сумел достать подробный план этажа здания, с указанием расположения всех документов. В здании имеются двери, для открытия которых требуются ключи. У Джона имеется несколько ключей. Некоторые ключи расположены и в самом здании.
Помогите Джону выяснить, сколько документов он может украсть.
\InputFile
Первая строка состоит из нескольких тестов, не более \textbf{100}. Каждый тест состоит из:
\begin{itemize}
\item одна строка с двумя целыми числами \textbf{h} и \textbf{w} (\textbf{2} ≤ \textbf{h}, \textbf{w} ≤ \textbf{100}): высота и ширина карты.
\item \textbf{h} строк по \textbf{w} символов, описывающих карту:
\begin{itemize}
\item '\textbf{.}' - пустое место.
\item '\textbf{*}' - непроходимая стена.
\item '\textbf{\$}' - документ, который Джон хочет украсть.
\item буква верхнего регистра - дверь.
\item буква нижнего регистра - ключ, открывающий дверь с соответствующей буквой верхнего регистра.
\end{itemize}
\item одна строка из различных букв нижнего регистра: ключи, имеющиеся у Джона. Если у него ключей нет, то строка содержит "\textbf{0}".
\end{itemize}
Джон может свободно передвигаться с внешней стороне здания. Для любой двери количество ключей, которые ее открывают, может равняться нулю, одному, или быть больше одного. Для любого ключа количество дверей, которые он открывает, может равняться нулю, одному, или быть больше одного. Ключи могут быть использованы повторно.
\OutputFile
Для каждого теста вывести в отдельной строке общее количество документов, которое сможет украсть Джон.
Вхідні дані #1
3 5 17 ***************** .............**$* *B*A*P*C**X*Y*.X. *y*x*a*p**$*$**$* ***************** cz 5 11 *.********* *...*...*x* *X*.*.*.*.* *$*...*...* *********** 0 7 7 *ABCDE* X.....F W.$$$.G V.$$$.H U.$$$.J T.....K *SQPML* irony
Вихідні дані #1
3 1 0