Das 21. Jahrhundert ist das Jahrhundert der Lebenswissenschaften. Die Menschheit investiert große personelle und materielle Ressourcen in deren Erforschung, um die Überlebensmechanismen verschiedener Lebewesen besser zu verstehen, sich selbst besser kennenzulernen und die Lebensqualität zu verbessern. Die Regierung des Landes Q beginnt zunächst mit Forschungen zur Geschlechtsänderung bei Schafen. Sie hofft, durch eine Geschlechtsänderung mittels genetischer Rekombination die Überlebensfähigkeit der gesamten Schafpopulation zu erhöhen. Gelingt dieses Forschungsvorhaben, wird die Menschheit über eine futuristische Technologie verfügen, mit der sich das Geschlecht von Tieren beliebig ändern lässt. Dies wäre ein wichtiger Meilenstein in der Geschichte der Lebenswissenschaften.
Die Regierung des Landes Q wählt $M$ Schafe als Versuchstiere aus. Unter diesen $M$ Schafen gibt es $K$ eingeschlechtliche Abstammungsketten der Länge $N$. Eine „Abstammungskette“ ist eine Kette aus Vater-/Mutter-Kind-Beziehungen, beispielsweise Großvater–Vater–Sohn. „Eingeschlechtlich“ bedeutet, dass alle Individuen einer solchen Kette dasselbe Geschlecht haben, also alle männlich oder alle weiblich sind. Die Länge einer Abstammungskette ist die Anzahl ihrer Individuen; Großvater–Vater–Sohn ist beispielsweise eine Kette der Länge 3. Diese $K$ Abstammungsketten überschneiden sich nicht.
Nicht jedes Schaf muss zu einer Abstammungskette gehören; manche Schafe gehören möglicherweise zu keiner, daher gilt $NK\le M$. Neben den Abstammungsketten gibt es zwischen Schafen derselben Generation auch „Fortpflanzungsbeziehungen“. Haben zwei Schafe unterschiedlichen Geschlechts bereits gemeinsame Nachkommen gezeugt, besteht zwischen ihnen eine solche Beziehung. Fortpflanzungsbeziehungen treten nur zwischen Schafen unterschiedlichen Geschlechts derselben Generation auf. „Dieselbe Generation“ bedeutet hier dieselbe Generationenstufe: Ein Schaf kann nur mit Schafen aus der Generation seiner Geschwister eine Fortpflanzungsbeziehung haben, nicht mit Eltern, Kindern oder Angehörigen weiter entfernter Generationen.
Eine Geschlechtsänderung bei einem Schaf verursacht hohe Versuchskosten. Die Änderung des Geschlechts von Schaf $i$ kostet $c_i$. Außerdem beeinflussen Geschlechtsänderungen die Stabilität der Fortpflanzungsbeziehungen. Jede Fortpflanzungsbeziehung $j$ besitzt eine Anfangsstabilität $b_j$ und einen Abschwächungsfaktor $d_j$. Nach Abschluss aller Geschlechtsänderungen gilt: Haben beide Partner ihr Geschlecht behalten, ist die Stabilität $s_j=b_j$; wurden die Geschlechter beider Partner vertauscht, ist sie $s_j=\lfloor b_jd_j\rfloor$; in allen anderen Fällen ist sie $s_j=0$.
Gegeben sind das Geschlecht jedes Schafes, seine Änderungskosten sowie alle Abstammungsketten und Fortpflanzungsbeziehungen. Die Regierung des Landes Q möchte, dass Sie einen Plan zur Geschlechtsänderung entwerfen, der den Gesamtertrag maximiert. Der Ertrag wird wie folgt berechnet:
$$ Profit=\lfloor 10\ln(1+A)\rfloor\cdot S-C. $$
Dabei ist $A$ die Anzahl benachbarter Paare in den Abstammungsketten, deren Partner nach den Änderungen unterschiedliche Geschlechter haben. $S$ ist die Summe der Stabilitäten aller Fortpflanzungsbeziehungen nach den Änderungen, also $S=\sum_j s_j$. $C$ ist die Summe der Kosten für die Geschlechtsänderungen der Schafe, also $C=\sum_i c_i$.
Eingabe
Die Eingabedatei heißt gender.in.
Die erste Zeile enthält vier nichtnegative ganze Zahlen $N,K,M,P$: die Länge der Abstammungsketten, ihre Anzahl, die Gesamtzahl der Schafe in der Versuchsgruppe und die Anzahl der Fortpflanzungsbeziehungen.
Die zweite Zeile enthält eine Zeichenkette mit $M$ Zeichen, die jeweils M oder F sind und die anfänglichen Geschlechter der $M$ Schafe beschreiben. M steht für männlich und F für weiblich.
Die dritte Zeile enthält $M$ positive ganze Zahlen $c_i$, die Kosten für die Geschlechtsänderung jedes Schafes.
Die folgenden $K$ Zeilen enthalten jeweils $N$ ganze Zahlen und beschreiben die Schafnummern in den $K$ Abstammungsketten. Alle Schafe sind mit ganzen Zahlen von $1$ bis $M$ nummeriert. Es ist garantiert, dass die Schafe jeder Kette dasselbe Geschlecht haben und die Ketten sich nicht überschneiden.
Die folgenden $P$ Zeilen enthalten jeweils drei positive ganze Zahlen $x,y,b$ und eine reelle Zahl $d$. Sie geben an, dass zwischen Schaf $x$ und Schaf $y$ eine Fortpflanzungsbeziehung mit Anfangsstabilität $b$ und Abschwächungsfaktor $d$ besteht. Es ist garantiert, dass $x$ und $y$ anfangs unterschiedliche Geschlechter haben und derselben Generation angehören. Jede Beziehung wird in den Daten nur einmal beschrieben.
Ausgabe
Die Ausgabedatei gender.out enthält genau eine Zeile mit einer ganzen Zahl: dem größtmöglichen Ertrag des Änderungsplans.
Beispiele
Eingabe 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
Ausgabe 1
360
Hinweis
Die Geschlechter werden zu MMFFFM geändert. Der Ertrag beträgt $\lfloor 10\ln(1+2)\rfloor\times(20+18)-(10+10)=360$.
Es gilt $A=2$, weil in der Abstammungskette $1-2-3$ die Schafe $2$ und $3$ unterschiedliche Geschlechter haben und in der Kette $4-5-6$ die Schafe $5$ und $6$ unterschiedliche Geschlechter haben.
Eingabe 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
Ausgabe 2
888
Hinweis
Die Geschlechter werden zu FMFMFMM geändert. Der Ertrag beträgt $\lfloor 10\ln(1+4)\rfloor\times(20+18+20)-(10+10+10+10)=888$.
Es gilt $A=4$, weil in der Abstammungskette $1-2-3$ die Schafe $1$ und $2$ sowie $2$ und $3$ unterschiedliche Geschlechter haben; in der Kette $4-5-6$ haben $4$ und $5$ sowie $5$ und $6$ unterschiedliche Geschlechter. Insgesamt sind es 4 Paare.
Beispiel 3
Siehe gender/gender.in und gender/gender.ans im Teilnehmerverzeichnis.
Beschränkungen
Für 10 % der Daten gilt $M\le 20$.
Für 10 % der Daten gilt $d_j=0$.
Für 10 % der Daten gilt $d_j=0.5$.
Diese drei Datengruppen sind paarweise disjunkt.
Für 100 % der Daten gilt $N\le 50$, $K\le 4$, $M\le 1000$, $P\le 10000$, $0.0\le d_j\le 1.0$. Sowohl $b_j$ als auch $c_i$ sind höchstens $10000$, und $d_j$ hat höchstens 6 Nachkommastellen.