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