License plates#4059
The rapid increase in the number of cars in the country has resulted in a shortage of license plates.
A committee was established to design a new plate format, and they decided on the following guidelines:
The plate must consist of characters.
To facilitate memorization, all allowable characters for the plate are divided into distinct groups (such as letters and numbers). A character cannot belong to more than one group.
Characters from each group must be placed in specific positions as defined by a mask. For example, with the mask "ldddll" where represents a letter and represents a digit, a valid plate could be "a264bc".
No two characters on the plate can be identical to avoid "fancy" plates.
Your task is to determine the maximum number of unique plates that can be generated based on the character groups and their designated mask.
The first line contains a single integer – the number of character groups (1 \leq n \leq 9).
The following lines describe the character groups. Each line includes two integers and , separated by a space, where is the group number (1 \leq k \leq n), and is the number of characters in that group (1 \leq c \leq 15).
The last line contains the plate mask, where each digit indicates the group number from which a character must be placed in the corresponding position. The mask has at least one character and does not exceed characters in length. It is guaranteed that each digit in the mask is between and .
The output should be a single integer representing the maximum number of unique plates that can be created under these conditions. If no plate can be created, output .
Example 1