eolymp
bolt
Try our new interface for solving problems
Məsələlər

Автомобильные номера

Автомобильные номера

Zaman məhdudiyyəti 0.4 saniyə
Yaddaşı istafadə məhdudiyyəti 16 MiB

Резкое увеличение количества машин в стране привело к нехватке автомобильных номеров.

Для разработки формата нового номера была создана комиссия, которая пришла к выводу, что:

  • номер должен состоять из m символов;

  • для обеспечения простоты запоминания номера все допустимые в номере символы должны быть разбиты на группы (например, буквы и цифры). Один и тот же символ не может входить в несколько групп;

  • символы, принадлежащие каждой из групп, должны располагаться в строго отведенных местах, заданных маской (например, для маски "бцццбб" где б – это символ из группы букв, а ц – символ из группы цифр, допустимым будет номер "в264ро");

  • в номере не может быть двух одинаковых символов для обеспечения отсутствия "красивых" номеров.

Требуется по списку групп символов и маске их расположения в номере определить максимальное количество номеров, которые могут быть созданы.

Giriş verilənləri

Первая строка содержит одно целое число n – количество групп символов (1n9).

Следующие n строк содержат описания групп символов. Каждая строка состоит из двух целых чисел k и c, разделенных пробелом, где k – номер группы символов (1kn), а c – количество символов в группе (1c15).

Последняя строка содержит маску номера, в которой каждая цифра определяет номер группы, символ из которой должен располагаться в указанном месте. Строка имеет хотя бы один символ и ее длина не превышает 15 символов. Гарантируется, что каждая цифра в строке находится в диапазоне от 1 до n.

Çıxış verilənləri

Выходной файл должен содержать одно целое число – максимальное количество номеров, которые могут быть созданы для заданных условий. Если ни один номер не может быть создан, то вывести 0.

Nümunə

Giriş verilənləri #1
2
1 3
2 4
1221
Çıxış verilənləri #1
72
Mənbə Региональная олимпиада по программированию, СибГИУ, 2011