El siglo XXI es el siglo de las ciencias de la vida. La humanidad dedica grandes recursos humanos y materiales a investigarlas para comprender mejor los mecanismos de supervivencia de los seres vivos, conocerse mejor a sí misma y mejorar la calidad de vida. El gobierno del país Q ha comenzado a estudiar la modificación del sexo en ovejas, con la esperanza de aumentar la capacidad de supervivencia de toda la población mediante cambios de sexo por recombinación genética. Si este proyecto tiene éxito, la humanidad dominará una tecnología revolucionaria capaz de cambiar a voluntad el sexo de los animales, lo que constituirá un hito importante en la historia de las ciencias de la vida.
El gobierno de Q ha seleccionado $M$ ovejas como muestra experimental. Entre ellas existen $K$ cadenas de parentesco de un solo sexo y de longitud $N$. Una «cadena de parentesco» está formada por relaciones de padre o madre con hijo o hija; por ejemplo, abuelo–padre–hijo es una cadena. «De un solo sexo» significa que todos los individuos de cada cadena son del mismo sexo, todos machos o todas hembras. La longitud es la cantidad de individuos de la cadena: abuelo–padre–hijo tiene longitud 3. Estas $K$ cadenas no se intersectan.
No es necesario que cada oveja pertenezca a una cadena; algunas pueden no pertenecer a ninguna, por lo que $NK\le M$. Además del parentesco, entre ovejas de la misma generación existen «relaciones reproductivas». Dos ovejas de distinto sexo que hayan tenido descendencia tienen una relación reproductiva. Estas relaciones solo existen entre individuos de distinto sexo y de la misma generación: es decir, una oveja solo las tiene con ovejas de la generación de sus hermanos, y no con sus padres, hijos ni otras generaciones más lejanas.
Cambiar el sexo de una oveja requiere grandes gastos experimentales. Cambiar el sexo de la oveja $i$ cuesta $c_i$. Además, los cambios afectan a la estabilidad de las relaciones reproductivas. Cada relación $j$ tiene una estabilidad inicial $b_j$ y un coeficiente de atenuación $d_j$. Una vez terminados todos los cambios, si ninguno de los dos individuos ha cambiado de sexo, la estabilidad es $s_j=b_j$; si ambos han intercambiado sus sexos, es $s_j=\lfloor b_jd_j\rfloor$; en cualquier otro caso, es $s_j=0$.
Dados el sexo y el coste de modificación de cada oveja, todas las cadenas de parentesco y todas las relaciones reproductivas, el gobierno de Q quiere que diseñes un plan de modificación que maximice el beneficio total, calculado así:
$$Profit=\lfloor10\ln(1+A)\rfloor\cdot S-C.$$
Aquí, $A$ es la cantidad de pares adyacentes de las cadenas de parentesco que tienen distinto sexo tras las modificaciones; $S$ es la suma de las estabilidades de las relaciones reproductivas tras las modificaciones, es decir, $S=\sum_j s_j$; y $C$ es la suma de los costes de cambiar el sexo de las ovejas, es decir, $C=\sum_i c_i$.
Entrada
El archivo de entrada es gender.in.
La primera línea contiene cuatro enteros no negativos $N,K,M,P$: la longitud de las cadenas de parentesco, la cantidad de cadenas, el número total de ovejas de la muestra y la cantidad de relaciones reproductivas, respectivamente.
La segunda línea contiene una cadena de $M$ caracteres, cada uno M o F, que describe el sexo inicial de las $M$ ovejas. M indica macho y F indica hembra.
La tercera línea contiene $M$ enteros positivos $c_i$, los costes de cambiar el sexo de cada oveja.
Las siguientes $K$ líneas contienen $N$ enteros cada una, que describen los números de las ovejas de cada cadena. Todas las ovejas están numeradas de $1$ a $M$. Se garantiza que las ovejas de cada cadena son del mismo sexo y que las cadenas no se superponen.
Las siguientes $P$ líneas contienen cada una tres enteros positivos $x,y,b$ y un real $d$, indicando una relación reproductiva entre las ovejas $x$ e $y$, de estabilidad inicial $b$ y coeficiente de atenuación $d$. Se garantiza que $x$ e $y$ tienen distinto sexo inicialmente y son de la misma generación. Cada relación se describe una sola vez.
Salida
El archivo de salida gender.out contiene una sola línea con un entero: el máximo beneficio del plan de modificación.
Ejemplos
Entrada 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
Salida 1
360
Nota
Modifica los sexos para obtener MMFFFM. El beneficio es $\lfloor10\ln(1+2)\rfloor\times(20+18)-(10+10)=360$.
Se tiene $A=2$ porque en la cadena $1-2-3$ las ovejas $2$ y $3$ tienen distinto sexo, y en la cadena $4-5-6$ las ovejas $5$ y $6$ tienen distinto sexo.
Entrada 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
Salida 2
888
Nota
Modifica los sexos para obtener FMFMFMM. El beneficio es $\lfloor10\ln(1+4)\rfloor\times(20+18+20)-(10+10+10+10)=888$.
Se tiene $A=4$ porque en la cadena $1-2-3$ las ovejas $1$ y $2$ tienen distinto sexo, al igual que las ovejas $2$ y $3$; en la cadena $4-5-6$ las ovejas $4$ y $5$ tienen distinto sexo, al igual que las ovejas $5$ y $6$. En total hay 4 pares de distinto sexo.
Ejemplo 3
Consulta gender/gender.in y gender/gender.ans en el directorio del participante.
Restricciones
Para el $10\%$ de los datos, $M\le20$.
Para el $10\%$ de los datos, $d_j=0$.
Para el $10\%$ de los datos, $d_j=0.5$.
Estas tres categorías de datos son disjuntas dos a dos.
Para el $100\%$ de los datos, $N\le50$, $K\le4$, $M\le1000$, $P\le10000$, $0.0\le d_j\le1.0$; tanto $b_j$ como $c_i$ son como máximo $10000$, y $d_j$ tiene como máximo 6 cifras decimales.