Maximizing Profit via Gender Modification in Sheep

In the 21st century, life science research has reached unprecedented heights. Q Country is conducting experiments on sheep in order to improve the survival ability of the entire flock by modifying their gender through gene recombination. A total of M sheep have been selected for experiments. Among these, there are K disjoint genealogical (blood) chains, each of length N. A genealogical chain is defined as a sequence of individuals connected by a parent–child relation (for example, grandfather–father–son). Each chain is of a single sex, meaning all individuals in the chain have the same sex.

Note that not every sheep belongs to a chain, so it is possible that N * K ≤ M. Besides the genealogical chains, there exist breeding relationships among sheep of the same generation. Two sheep of opposite sex that have produced offspring in the past form a breeding relationship. Such a relationship only occurs between peers (i.e. siblings), and no relationship exists between sheep of different generations.

Changing the gender of sheep is expensive. Modifying the gender of sheep i requires a cost of c_i. In addition, modifying gender may affect the stability of breeding relationships. For each breeding relationship j, its initial stability is b_j and it has a decay coefficient d_j. After all modifications are completed, if both sheep in the relationship have not been modified then the relationship’s stability s_j remains b_j; if both sheep are modified then the stability becomes \( \lfloor b_j\,d_j \rfloor \); otherwise, the stability becomes 0.

The overall profit is calculated as follows:

[ P = \lfloor 10 \ln(1 + A) \rfloor \times S - C, ]

where:

• A is the total number of adjacent pairs (in each chain) that are of opposite gender after the modifications. In each chain, for every adjacent pair, if the two sheep have different genders after modifications, it counts as one.
• S is the sum of the stabilities of all breeding relationships, i.e. \( S = \sum_j s_j \).
• C is the total cost incurred by modifying the genders, i.e. \( C = \sum_i c_i \) (summed over every sheep whose gender was changed).

Your task is to choose a set of sheep to modify (or not) to maximize the profit P.

Input constraints: To allow an exponential solution, you may assume that M ≤ 16 and that indices in genealogical chains are 1-indexed. Breeding relationships are only defined between two sheep which originally had opposite genders.

inputFormat

The input begins with a line containing four integers M K N R:

• M: total number of sheep.
• K: number of genealogical chains.
• N: length of each genealogical chain.
• R: number of breeding relationships.

The next line contains M space‐separated integers c1, c2, ..., cM representing the cost to modify each sheep’s gender.

The third line contains M space‐separated characters (each either M or F) representing the initial gender of each sheep (sheep 1 through sheep M).

Then follow K lines. Each of these lines contains N integers, representing the indices (1-indexed) of the sheep in one genealogical chain (in order).

Finally, there are R lines, each describing one breeding relationship with four values: u v b d, where u and v are the indices of the two sheep (which originally have opposite genders), b is the initial stability, and d is the decay coefficient. Note that d is a decimal number. For a modified pair, the resulting stability is \( \lfloor b \times d \rfloor \).

outputFormat

Output a single integer — the maximum profit P that can be achieved.

Note: Use natural logarithm (ln) and the floor function as defined in the problem statement.

sample

3 1 2 1
5 3 4
M F M
1 2
2 3 10 0.5

60