Задачи
Автомобильные номера
Автомобильные номера
Резкое увеличение количества машин в стране привело к нехватке автомобильных номеров.
Для разработки формата нового номера была создана комиссия, которая пришла к выводу, что:
\begin{itemize}
\item номер должен состоять из \textbf{m} символов;
\item для обеспечения простоты запоминания номера все допустимые в номере символы должны быть разбиты на группы (например, буквы и цифры). Один и тот же символ не может входить в несколько групп;
\item символы, принадлежащие каждой из групп, должны располагаться в строго отведенных местах, заданных маской (например, для маски "бцццбб" где \textbf{б} -- это символ из группы букв, а \textbf{ц} -- символ из группы цифр, допустимым будет номер "в264ро");
\item в номере не может быть двух одинаковых символов для обеспечения отсутствия "красивых" номеров.
\end{itemize}
Требуется по списку групп символов и маске их расположения в номере определить максимальное количество номеров, которые могут быть созданы.
\InputFile
Первая строка содержит одно целое число \textbf{n} -- количество групп символов (\textbf{1} ≤ \textbf{n} ≤ \textbf{9}).
Следующие \textbf{n} строк содержат описания групп символов. Каждая строка состоит из двух целых чисел \textbf{k} и \textbf{c}, разделенных пробелом, где \textbf{k} -- номер группы символов (\textbf{1} ≤ \textbf{k} ≤ \textbf{n}), а \textbf{c} -- количество символов в группе (\textbf{1} ≤ \textbf{c} ≤ \textbf{15}).
Последняя строка содержит маску номера, в которой каждая цифра определяет номер группы, символ из которой должен располагаться в указанном месте. Строка имеет хотя бы один символ и ее длина не превышает \textbf{15} символов. Гарантируется, что каждая цифра в строке находится в диапазоне от \textbf{1} до \textbf{n}.
\OutputFile
Выходной файл должен содержать одно целое число -- максимальное количество номеров, которые могут быть созданы для заданных условий. Если ни один номер не может быть создан, то вывести \textbf{0}.
Входные данные #1
2 1 3 2 4 1221
Выходные данные #1
72