License plates
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 m 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 "lnddll" where l represents a letter and n represents a number, 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.
Input
The first line contains a single integer n – the number of character groups (1 ≤ n ≤ 9).
The following n lines describe the character groups. Each line includes two integers k and c, separated by a space, where k is the group number (1 ≤ k ≤ n), and c is the number of characters in that group (1 ≤ c ≤ 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 15 characters in length. It is guaranteed that each digit in the mask is between 1 and n.
Output
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 0.