Le XXIe siècle est celui des sciences du vivant. L'humanité consacre d'importants moyens humains et matériels à leur étude, afin de mieux comprendre les mécanismes de survie des différentes espèces, de mieux se connaître elle-même et d'améliorer la qualité de vie. Le gouvernement du pays Q a commencé par étudier la modification du sexe chez les moutons. Il espère renforcer la capacité de survie de toute la population en changeant leur sexe par recombinaison génétique. Si ce projet aboutit, l'humanité maîtrisera une technologie révolutionnaire permettant de changer à volonté le sexe des animaux, ce qui constituera une étape majeure dans l'histoire des sciences du vivant.
Le gouvernement a choisi $M$ moutons comme échantillon expérimental. Parmi eux se trouvent $K$ chaînes de filiation de longueur $N$, chacune constituée d'individus d'un même sexe. Une « chaîne de filiation » est une chaîne de relations parent-enfant, par exemple grand-père–père–fils. « D'un même sexe » signifie que tous les individus d'une chaîne sont mâles ou tous femelles. La longueur d'une chaîne est son nombre d'individus ; ainsi, grand-père–père–fils est de longueur $3$. Ces $K$ chaînes sont disjointes.
Tous les moutons ne doivent pas nécessairement appartenir à une chaîne : certains peuvent n'appartenir à aucune, donc $NK\le M$. Outre les chaînes de filiation, il existe des « relations de reproduction » entre moutons d'une même génération. Deux moutons de sexes opposés ont une telle relation s'ils ont déjà eu une descendance ensemble. Ces relations n'existent qu'entre individus de sexes opposés et de même génération : un mouton ne peut en avoir qu'avec des individus de la génération de ses frères et sœurs, et jamais avec ses parents, ses enfants ou des générations plus éloignées.
Changer le sexe d'un mouton coûte très cher : le coût pour le mouton $i$ est $c_i$. Cela modifie aussi la stabilité des relations de reproduction. Chaque relation $j$ possède une stabilité initiale $b_j$ et un coefficient d'atténuation $d_j$. Une fois toutes les modifications terminées, si aucun des deux sexes n'a changé, sa stabilité vaut $s_j=b_j$ ; si les deux partenaires ont échangé leurs sexes, elle vaut $s_j=\lfloor b_jd_j\rfloor$ ; dans les autres cas, $s_j=0$.
Étant donnés le sexe de chaque mouton, son coût de modification, toutes les chaînes de filiation et toutes les relations de reproduction, le gouvernement souhaite que vous conceviez un plan maximisant le bénéfice total. Celui-ci est calculé par :
$$ Profit=\lfloor10\ln(1+A)\rfloor\cdot S-C $$
où $A$ est le nombre de paires d'individus consécutifs dans les chaînes de filiation qui sont de sexes opposés après modification, $S$ est la somme des stabilités des relations après modification, soit $S=\sum_j s_j$, et $C$ est la somme des coûts des changements de sexe effectués, soit $C=\sum_i c_i$.
Entrée
Le fichier d'entrée est gender.in.
La première ligne contient quatre entiers non négatifs $N,K,M,P$ : la longueur des chaînes, leur nombre, le nombre total de moutons dans l'échantillon et le nombre de relations de reproduction.
La deuxième ligne contient une chaîne de $M$ caractères, chacun étant M ou F, décrivant les sexes initiaux des $M$ moutons. M signifie mâle et F femelle.
La troisième ligne contient $M$ entiers positifs $c_i$, les coûts de changement de sexe des moutons.
Les $K$ lignes suivantes contiennent chacune $N$ entiers décrivant les numéros des moutons d'une chaîne. Tous les moutons sont numérotés de $1$ à $M$. Il est garanti que tous les moutons d'une chaîne sont du même sexe et que les chaînes ne se chevauchent pas.
Les $P$ lignes suivantes contiennent chacune trois entiers positifs $x,y,b$ et un réel $d$, indiquant une relation de reproduction entre les moutons $x$ et $y$, de stabilité initiale $b$ et de coefficient d'atténuation $d$. Il est garanti que $x$ et $y$ sont initialement de sexes différents et de même génération. Chaque relation n'est décrite qu'une fois.
Sortie
Le fichier gender.out contient une seule ligne avec un entier : le bénéfice maximal du plan de modification.
Exemples
Entrée 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
Sortie 1
360
Remarque
On obtient les sexes MMFFFM. Le bénéfice vaut $\lfloor10\ln(1+2)\rfloor\times(20+18)-(10+10)=360$.
$A=2$, car dans la chaîne $1-2-3$, les moutons $2$ et $3$ sont de sexes différents, et dans la chaîne $4-5-6$, les moutons $5$ et $6$ sont de sexes différents.
Entrée 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
Sortie 2
888
Remarque
On obtient les sexes FMFMFMM. Le bénéfice vaut $\lfloor10\ln(1+4)\rfloor\times(20+18+20)-(10+10+10+10)=888$.
$A=4$, car dans la chaîne $1-2-3$, les moutons $1$ et $2$ sont de sexes différents, tout comme $2$ et $3$ ; dans la chaîne $4-5-6$, les moutons $4$ et $5$ sont de sexes différents, tout comme $5$ et $6$. Cela fait $4$ paires au total.
Exemple 3
Voir gender/gender.in et gender/gender.ans dans le répertoire du participant.
Contraintes
Pour $10\%$ des données, $M\le20$.
Pour $10\%$ des données, $d_j=0$.
Pour $10\%$ des données, $d_j=0.5$.
Ces trois catégories sont deux à deux disjointes.
Pour $100\%$ des données, $N\le50$, $K\le4$, $M\le1000$, $P\le10000$, $0.0\le d_j\le1.0$ ; $b_j$ et $c_i$ ne dépassent pas $10000$, et $d_j$ possède au plus $6$ chiffres après la virgule.