Voltage Stabilization Components Installation

A renowned chip company requires you to install voltage stabilizing components on their latest products. Each chip is designed as an $N \times N$ square board with slots. Some slots are unavailable (represented by '/'), and some are already occupied by components (represented by 'C'). The remaining available slots (represented by '.') can be used to add new components.

However, for electrical stability you must satisfy the following constraints:
1. For each row $i$, you are given a non-negative integer $T_i$ and $T_i$ column indices $r_{i,1}, r_{i,2}, \ldots, r_{i,T_i}$. It must hold that
[ R_i \leq C_{r_{i,1}} + C_{r_{i,2}} + \cdots + C_{r_{i,T_i}}, ] where $R_i$ is the total number of components in row $i$ (including pre-occupied slots) and $C_j$ is the total number of components in column $j$.

2. For each row $i$, a floating-point number $s_i$ ($0 \leq s_i \leq 1$) is given. The number of components in row $i$ must not exceed $s_i$ times the total components on the chip, i.e., [ R_i \leq s_i \cdot X, ] where $X$ is the total number of components on the chip.

3. For each column $j$, a floating-point number $t_j$ ($0 \leq t_j \leq 1$) is provided. The number of components in column $j$ must not exceed $t_j$ times the total components, i.e., [ C_j \leq t_j \cdot X. ]

Your task is to insert as many additional components as possible into available slots, while obeying all the above constraints. Note that the already occupied slots are counted in the totals.

inputFormat

The first line contains an integer $N$, denoting the size of the chip (the chip is an $N \times N$ board).

The next $N$ lines each contain a string of length $N$, consisting of characters '.', '/', and 'C', representing available slots, unavailable slots, and pre-occupied slots, respectively.

Then follow $N$ lines, one per row $i$ (1-indexed). Each such line begins with an integer $T_i$, followed by $T_i$ integers (the column indices $r_{i,1}, r_{i,2}, \ldots, r_{i,T_i}$) and a floating point number $s_i$.

The last line contains $N$ floating point numbers, representing $t_1, t_2, \ldots, t_N$.

outputFormat

Output a single integer: the maximum number of additional components that can be inserted while satisfying all given constraints.

sample

3
.C.
/..
...
1 2 0.5
0 1.0
2 1 3 0.7
0.6 0.8 1.0

1