Автомобільні номери#4059
Різке збільшення кількості автомобілів у країні призвело до нестачі автомобільних номерів.
Для розробки формату нового номеру була створена комісія, яка прийшла до висновку, що:
номер повинен складатись з символів;
для забезпечення простоти запам'ятовування номера усі допустимі у номері символи повинні бути розбиті на групи (наприклад, букви та цифри). Один і той самий символ не може входити у декілька груп;
символи, які належать кожній з груп, повинні розміщуватись у строго відведених місцях, заданих маскою (наприклад, для маски "бцццбб" де – це символ з групи букв, а – символ з групи цифр, допустимим буде номер "в264ро");
у номері не може бути двох однакових символів для забезпечення відсутності "красивих" номерів.
Потрібно по списку груп символів та масці їх розміщення у номері визначити максимальну кількість номерів, які можуть бути створені.
Перший рядок містить одне ціле число – кількість груп символів (1 \leq n \leq 9).
Наступні рядків містять описи груп символів. Кожен рядок складається з двох цілих чисел та , відокремлених пропуском, де – номер групи символів (1 \leq k \leq n), а – кількість символів у групі (1 \leq c \leq 15).
Останній рядок містить маску номера, у якій кожна цифра визначає номер групи, символ з якої повинен розміщуватись у вказаному місці. Рядок має хоча б один символ і його довжина не перевищує символів. Гарантується, що кожна цифра у рядку знаходиться у діапазоні від до .
Вихідний файл повинен містити одне ціле число – максимальну кількість номерів, які можуть бути створені при заданих умовах. Якщо жоден номер не може бути створеним, то вивести .
Приклад 1