Exam#700

Exam

2 seconds

64 megabytes

Hard

Many universities use a scoring system in which students can earn up to $100$ points, with up to $75$ points during the semester and up to $25$ points in the final exam. The final grade depends on the total sum of semester and exam points according to a specific table.

If a student earns strictly fewer than $35$ points during the semester, they are not allowed to take the exam; assume that the names of such students are excluded from the list.

If you look at the column of European marks in the exam list from top to bottom, you may find various "words". For example, if consecutive totals of points are $92$ , $75$ , and $66$ , they are marked as $A$ , $C$ , and $E$ respectively, thus forming the word $A C E$ . In the case of $F X$ , both letters (first $F$ , then $X$ ) appear in the word.

An exam is a risky event, and its results cannot be known in advance. However, the lecturer knows the approximate level of knowledge of each student and the list of exam questions. Therefore, the lecturer can estimate the probabilities for each student to score every possible number of exam points: the probability that the student gets $0$ points, $1$ point, ..., $25$ points — a total of $26$ non-negative integers, whose sum is $100$ . The number of semester points earned by each student is also known (these are fixed integers from $35$ to $75$ , with no probabilities).

The lecturer is a great esthete and dislikes situations where the "word" formed by the European grades contains any "unpleasant" substring (that is, as a consecutive sequence of letters).

Your task is to write a program to compute the probability that the esthete lecturer will be satisfied because none of the "unpleasant" substrings occur.

Input

The first line contains the number of test cases. Each test case starts with the number of students $N$ ( $3 \leq N \leq 100$ 3 \leq N \leq 100). Each of the next $N$ lines contains $27$ space-separated integers: the number of semester points (from $35$ to $75$ ), and $26$ probabilities corresponding to exam results of $0, 1, \dots, 25$ 0, 1, \ldots, 25 points (each probability is non-negative, their sum is $100$ ). The next line of each test case contains the number $K$ ( $1 \leq K \leq 100$ 1 \leq K \leq 100) of "unpleasant" words. Each of the following $K$ lines contains an "unpleasant" word. Each of the $K$ lines contains only uppercase Latin letters (any letters, not just $A$ – $F$ and $X$ ). Each line contains between $2$ and $15$ letters and ends with the end-of-line symbol.

Output

Output a single real number — the calculated probability (in percent) that the lecturer will be satisfied, on a separate line. Any floating-point format is allowed (use a decimal point, not a decimal comma). *The answer will be accepted if its relative error does not exceed* $1 e-6$ .

Examples

Example 1

Note

The first student's sum is at least $72 + 10 = 82$ 72 + 10 = 82, so their grade cannot be $D$ . Thus, the "unpleasant" word $D E$ can only occur if the second student scores from $13$ to $19$ (probability $8% + 8% + 7% + 6% + 5% + 4% + 3% = 41%$ 8\% + 8\% + 7\% + 6\% + 5\% + 4\% + 3\% = 41\%) and the third from $5$ to $12$ ( $3% + 4% + 5% + 6% + 7% + 8% + 8% + 9% = 50%$ 3\% + 4\% + 5\% + 6\% + 7\% + 8\% + 8\% + 9\% = 50\%). Therefore, the probability of $D E$ appearing is $0.41 \times 0.5 = 0.205$ 0.41 \times 0.5 = 0.205, so it does not appear with probability $1 - 0.205 = 0.795$ 1 - 0.205 = 0.795 (i.e. $79.5%$ ).