Автомобильные номера
Резкое увеличение количества машин в стране привело к нехватке автомобильных номеров.
Для разработки формата нового номера была создана комиссия, которая пришла к выводу, что:
номер должен состоять из m символов;
для обеспечения простоты запоминания номера все допустимые в номере символы должны быть разбиты на группы (например, буквы и цифры). Один и тот же символ не может входить в несколько групп;
символы, принадлежащие каждой из групп, должны располагаться в строго отведенных местах, заданных маской (например, для маски "бцццбб" где б – это символ из группы букв, а ц – символ из группы цифр, допустимым будет номер "в264ро");
в номере не может быть двух одинаковых символов для обеспечения отсутствия "красивых" номеров.
Требуется по списку групп символов и маске их расположения в номере определить максимальное количество номеров, которые могут быть созданы.
Входные данные
Первая строка содержит одно целое число n – количество групп символов (1 ≤ n ≤ 9).
Следующие n строк содержат описания групп символов. Каждая строка состоит из двух целых чисел k и c, разделенных пробелом, где k – номер группы символов (1 ≤ k ≤ n), а c – количество символов в группе (1 ≤ c ≤ 15).
Последняя строка содержит маску номера, в которой каждая цифра определяет номер группы, символ из которой должен располагаться в указанном месте. Строка имеет хотя бы один символ и ее длина не превышает 15 символов. Гарантируется, что каждая цифра в строке находится в диапазоне от 1 до n.
Выходные данные
Выходной файл должен содержать одно целое число – максимальное количество номеров, которые могут быть созданы для заданных условий. Если ни один номер не может быть создан, то вывести 0.