Description

The 21st century is the century of life sciences. Humanity has invested extensive manpower and resources into life science research, aiming for a deeper understanding of the survival mechanisms of various organisms, so as to better understand ourselves and improve quality of life. The government of Country Q first launched gender modification research in sheep, hoping to enhance the survival ability of the entire sheep population by changing gender through gene recombination. If this plan succeeds, humans will master the black technology of arbitrarily changing animal gender, which will be an important milestone in the history of life science research.

The government of Country Q selects $M$ sheep from the flock as experimental samples. Among these $M$ sheep, there exist $K$ bloodline chains of length $N$, each of a single gender. A “bloodline chain” is a chain consisting of parent–child relationships, e.g., “grandfather – father – son” is a bloodline chain. “Single gender” means that all individuals in each bloodline chain are of the same gender, either all male or all female. The length of a bloodline chain is the number of individuals in the chain, e.g., “grandfather – father – son” has length $3$. These $K$ bloodline chains do not intersect.

Note that not every sheep must belong to a bloodline chain; some sheep might belong to none. Therefore, $N \times K \leq M$. Beyond the bloodline chains, there can also be “mating relationships” among same-generation sheep. Two opposite-sex sheep that have reproduced offspring form a “mating relationship.” Note that a mating relationship only occurs between opposite-sex individuals of the same generation. Here, “same generation” means they are of the same generation level, i.e., a sheep only forms mating relationships with its siblings’ generation, and never with its parents, children, or individuals of more distant generations.

Changing a sheep’s gender incurs a large experimental cost: changing the gender of sheep $i$ costs $c_i$. Furthermore, changing genders affects the stability of mating relationships: for each mating relationship $j$, there is an initial stability $b_j$ and an attenuation factor $d_j$. After all gender modifications are completed, if neither side’s gender changed, the stability is $s_j = b_j$; if both sides’ genders were flipped, then $s_j = \lfloor b_j d_j \rfloor$; in all other cases, $s_j = 0$.

Given each sheep’s gender, the gender change cost, all bloodline chains, and all mating relationships, Country Q asks you to design a gender modification plan to maximize the total profit. The profit is computed as follows:

Here $A$ is the number of adjacent pairs within the bloodline chains that are of opposite gender after modification, $S$ is the sum of the stabilities of all mating relationships after modification, i.e., $S = \sum\limits_j s_j$, and $C$ is the total cost of gender changes, i.e., $C = \sum\limits_i c_i$.

Input Format

• The first line contains four non-negative integers $N$, $K$, $M$, $P$, denoting the length of each bloodline chain, the number of bloodline chains, the total number of sheep in the sample, and the number of mating relationships, respectively.
• The second line is a string of $M$ characters, each being M or F, describing the initial gender of the $M$ sheep. M stands for male, F stands for female.
• The third line contains $M$ positive integers $c_i$, the cost to change the gender of each sheep.
• The next $K$ lines each contain $N$ integers, giving the indices (from $1$ to $M$) of the sheep in each of the $K$ bloodline chains. It is guaranteed that each chain is single-gender and that the chains are disjoint.
• The next $P$ lines each contain three integers $x$, $y$, $b$ and a real number $d$, indicating that sheep $x$ and sheep $y$ have a mating relationship with initial stability $b$ and attenuation factor $d$.

It is guaranteed that the initial genders of $x$ and $y$ are different, $x$ and $y$ are of the same generation, and each relationship appears at most once in the input.

Output Format

Output a single integer on one line, the maximum achievable profit under the modification plan.

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

360

Hint

Sample explanation: Change genders to MMFFFM. The profit is $\lfloor 10 \ln(1 + 2) \rfloor \times (20 + 18) - (10 + 10) = 360$. Here $A = 2$ because in bloodline chain $1 - 2 - 3$, sheep $2$ and $3$ are of different genders, and in bloodline chain $4 - 5 - 6$, sheep $5$ and $6$ are of different genders.

Constraints:

• For $10\%$ of the testdata, $M \leq 20$.
• For $10\%$ of the testdata, $d_j = 0$.
• For $10\%$ of the testdata, $d_j = 0.5$. These three categories are pairwise disjoint.
• For $100\%$ of the testdata, $1 \leq N \leq 50$, $1 \leq K \leq 4$, $1 \leq M \leq 10^3$, $1 \leq P \leq 10^4$, $0 \leq d_j \leq 1$, $0 \leq b_j, c_i \leq 10^4$, and the number of decimal places of $d_j$ does not exceed $6$.

Translated by ChatGPT 5