Різке збільшення кількості автомобілів у країні призвело до нехватки автомобільныи номерів. Для розробки формату нового номеру була створена комісія, яка прйишла до висновку, що: \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}.