The 21st century is the century of life sciences. Humanity has invested significant human and material resources into life science research, aiming to gain a deeper understanding of various biological organisms to better understand ourselves and improve the quality of life. The government of Country Q has pioneered research on gender modification in sheep, hoping to enhance the survival capabilities of the entire sheep population through gene recombination to alter gender. If this project is successfully researched, humanity will be able to change the gender of animals at will, which would be an important milestone in the history of life science research.
The government of Country Q has selected $M$ sheep as experimental samples. Among these $M$ sheep, there are $K$ lineage chains, each of length $N$, consisting of a single gender. A "lineage chain" is a chain formed by parent-child relationships, such as grandfather-father-son. "Single gender" means that the gender of every individual in each lineage chain is identical, either all male or all female. The length of a lineage chain refers to the number of individuals in the chain; for example, grandfather-father-son is a lineage chain of length 3. These $K$ lineage chains are disjoint.
Note that not every sheep must belong to a lineage chain; some sheep may not belong to any lineage chain, so $K \cdot N \le M$. In addition to lineage chains, sheep of the same generation also have "breeding relationships." If two sheep have ever produced offspring, a "breeding relationship" exists between them. Note that breeding relationships only occur between sheep of the same generation; here, "same generation" means that the two sheep have the same seniority, i.e., sheep only have "breeding relationships" with their siblings, not with their parents, children, or other more distant generations.
Modifying the gender of a sheep incurs a large experimental cost; modifying the gender of sheep $i$ costs $c_i$. In addition, modifying a sheep's gender will affect the stability of breeding relationships: each breeding relationship $j$ has an initial stability $b_j$ and a decay coefficient $d_j$. After all gender modification operations are completed, if the genders of both parties remain unchanged, the stability of this relationship is $s_j = b_j$; if the genders of both parties are swapped, the stability is $s_j = \lfloor b_j d_j \rfloor$; in other cases, the stability is $s_j = 0$.
Given the gender, gender modification cost, all lineage chain relationships, and breeding relationships for each sheep, the government of Country Q wants you to design a gender modification plan to maximize the total profit. The profit is calculated as follows: $$Profit = \lfloor 10 \ln(1 + A) \rfloor \cdot S - C$$ where $A$ is the number of adjacent pairs in the lineage chains that have different genders after modification, $S$ is the sum of the stabilities of the breeding relationships after modification, i.e., $S = \sum s_j$, and $C$ is the sum of the costs incurred by modifying the sheep's genders, i.e., $C = \sum c_i$.
Input
The first line contains four non-negative integers $N, K, M, P$, representing the length of the lineage chains, the number of lineage chains, the number of sheep in the experimental sample, and the number of breeding relationships, respectively.
The second line contains a string of $M$ characters, each being 'M' or 'F', describing the initial gender of these $M$ sheep. 'M' represents male, and 'F' represents female.
The third line contains $M$ positive integers $c_i$, representing the cost of modifying the gender of each sheep.
The next $K$ lines each contain $N$ integers, describing the sheep IDs in these $K$ lineage chains (all sheep are numbered with integers from 1 to $M$). It is guaranteed that the sheep in each chain are of the same gender, and the chains do not overlap.
The next $P$ lines each contain three positive integers $x, y, b$ and a real number $d$, representing that sheep $x$ and sheep $y$ have a breeding relationship, with an initial relationship stability of $b$ and a decay coefficient of $d$. It is guaranteed that the initial genders of $x$ and $y$ are different, and $x$ and $y$ are of the same generation. Each relationship is described only once in the data.
Output
The output file contains only one integer, representing the maximum profit of the modification plan.
Examples
Input 1
3 2 6 2 MMMFFF 10000 200 10 10000 200 10 1 2 3 4 5 6 2 5 20 0.1 3 6 20 0.9
Output 1
360
Note 1
The modified genders are MMFFFM. The profit is $\lfloor 10 \ln(1 + 2) \rfloor \times (20 + 18) - (10 + 10) = 360$. $A=2$ because in lineage chain 1-2-3, the genders of 2 and 3 are different, and in lineage chain 4-5-6, the genders of 5 and 6 are different.
Input 2
3 2 7 3 MMMFFFM 10 200 10 10 200 10 10 1 2 3 4 5 6 2 5 20 0.1 3 6 20 0.9 5 7 20 0.5
Output 2
888
Note 2
The modified genders are FMFMFMM. The profit is $\lfloor 10 \ln(1 + 4) \rfloor \times (20 + 18 + 20) - (10 + 10 + 10 + 10) = 888$. $A=4$ because in lineage chain 1-2-3, the genders of 1 and 2 are different, and 2 and 3 are different; in lineage chain 4-5-6, the genders of 4 and 5 are different, and 5 and 6 are different; totaling 4 differences.
Constraints
- For 10% of the data, $M \le 20$;
- For 10% of the data, $d_j = 0$;
- For 10% of the data, $d_j = 0.5$;
- The above three types of data are disjoint.
- For 100% of the data, $N \le 50, K \le 4, M \le 1000, P \le 10000, 0.0 \le d_j \le 1.0$.
- $b_j$ and $c_i$ are no greater than 10000, and the number of decimal places in $d_j$ does not exceed 6.