Circuit

A famous chip manufacturer wants to install components that can stabilize voltage on some of their latest products. Each chip is designed as an $N \times N$ square, and one slot can hold exactly one component. Your task is to insert as many of these components as possible.

Modern processor design is very complex. To stabilize the voltage, you must face the following constraints:

• Some slots are unusable.
• Some slots are already occupied by other components and therefore cannot be used for new components.
• Memory bus connections to the chip's horizontal and vertical boundaries require safe load voltages. Specifically, the chip provides $N$ row constraints and $N$ column constraints. For the $i$-th row constraint, given a non-negative integer $T_i$ and a list of column indices $r_{i1}, r_{i2}, \dots, r_{iT_i}$ ($1 \le j \le T_i$), the requirement is: the number of components in row $i$ must not exceed the specified total $T_i$ (i.e., the sum of components in column $r_{i1}$, column $r_{i2}$, $\dots$, column $r_{iT_i}$ must not exceed $T_i$).
• To avoid overheating, given floating-point numbers $s_i$ ($1 \le i \le N$) and $0 \le s_i \le 1$, the number of components in row $i$ must not exceed $s_i$ times the total number of components. Similarly, given floating-point numbers $t_i$ ($1 \le i \le N$) and $0 \le t_i \le 1$, the number of components in column $i$ must not exceed $t_i$ times the total number of components.

Note that the positions of already occupied slots are also counted in the total number of components. When calculating the total number of components on the chip, components already occupying slots must also be included.

The chip is described by an $N \times N$ matrix, where '.' represents an open slot, '/' represents an unusable slot, and 'C' represents a slot already occupied by a component.

Input

The first line contains an integer $N$ ($1 \le N \le 40$). Then $N$ lines follow, each containing $N$ characters describing the chip, with meanings as described above. After the $N$ lines, $N$ lines describe the constraints. Each line starts with a non-negative integer $T_i$, representing the constraint for row $i$. This is followed by $T_i$ distinct integers (all in the range $1$ to $N$), describing the relevant columns. The next line contains $N$ floating-point numbers $s_i$ ($1 \le i \le N$), each with at most three decimal places. The next line contains $N$ floating-point numbers $t_i$ ($1 \le i \le N$), each with at most three decimal places.

Output

If a valid strategy exists, output the maximum number of additional components that can be installed on the chip. Otherwise, output "impossible" (without quotes).

Constraints

• For 5% of the data, $1 \le N \le 4$.
• For 45% of the data, $T_i = 0$. Among these, 15% of the data has no already occupied slots.
• For 20% of the data, $T_i = 1$, and it is guaranteed that $r_{i1} = i$.
• For 100% of the data, $1 \le N \le 40$.

Examples

Input 1

5
CC/..
././/
..C.C
/.C..
/./C/
1 1
1 2
1 3
1 4
1 5
0.3 0.3 0.3 0.3 0.3
0.3 0.3 0.3 0.3 0.3

Output 1

7

Input 2

5
CC/..
././/
..C.C
/.C..
/./C/
1 1
1 2
1 3
1 4
1 5
0.2 0.2 0.2 0.2 0.2
0.2 0.2 0.2 0.2 0.2

Output 2

impossible

Note

For the first example, the number of components in each row and each column cannot exceed $3/10$ of the total, so the maximum number of components that can be installed on this $5 \times 5$ chip is 7. The figure below shows a feasible solution, where 'W' represents new components added to open slots.

CC/W.
W/W//
W.C.C
/.CWW
/W/C/

Figure 1. A feasible solution, where 'W' represents new components added to open slots.