O século XXI é o século das ciências da vida. A humanidade investe grandes recursos humanos e materiais nessa área para compreender mais profundamente os mecanismos de sobrevivência dos diversos seres vivos, conhecer melhor a si mesma e melhorar a qualidade de vida. O governo do país Q iniciou pesquisas sobre a alteração do sexo em ovinos, na esperança de aumentar a capacidade de sobrevivência de toda a população por meio da alteração do sexo por recombinação genética. Se esse projeto for bem-sucedido, a humanidade dominará uma tecnologia extraordinária que permite alterar livremente o sexo dos animais, um marco importante na história das ciências da vida.

O governo de Q selecionou $M$ ovinos como amostra experimental. Entre eles existem $K$ cadeias de parentesco de um único sexo, cada uma de comprimento $N$. Uma “cadeia de parentesco” é uma cadeia formada por relações entre pai ou mãe e filho ou filha; por exemplo, avô–pai–filho constitui uma cadeia. “De um único sexo” significa que todos os indivíduos de cada cadeia têm o mesmo sexo, sendo todos machos ou todos fêmeas. O comprimento de uma cadeia é seu número de indivíduos: avô–pai–filho é uma cadeia de comprimento 3. Essas $K$ cadeias não se intersectam.

Nem todo ovino precisa pertencer a uma cadeia: alguns podem não pertencer a nenhuma, portanto $NK\le M$. Além das cadeias de parentesco, existem “relações reprodutivas” entre ovinos da mesma geração. Dois ovinos de sexos opostos que já tiveram descendentes juntos possuem uma relação reprodutiva. Essas relações só existem entre indivíduos de sexos opostos da mesma geração. “Da mesma geração” significa que ambos têm a mesma posição geracional: um ovino só pode ter uma relação reprodutiva com indivíduos da geração de seus irmãos, e não com pais, filhos ou indivíduos de gerações mais distantes.

Alterar o sexo dos ovinos exige despesas experimentais elevadas: alterar o sexo do ovino $i$ custa $c_i$. Além disso, a alteração afeta a estabilidade das relações reprodutivas. Cada relação $j$ tem estabilidade inicial $b_j$ e fator de redução $d_j$. Após todas as alterações, se o sexo de ambos os indivíduos não mudou, a estabilidade da relação é $s_j=b_j$; se ambos trocaram de sexo, a estabilidade é $s_j=\lfloor b_jd_j\rfloor$; nos demais casos, $s_j=0$.

Dados o sexo de cada ovino, o custo de alterá-lo, todas as cadeias de parentesco e todas as relações reprodutivas, o governo de Q deseja que você elabore um plano de alteração de sexo que maximize o lucro. O lucro é calculado por:

$$Profit=\lfloor10\ln(1+A)\rfloor\cdot S-C.$$

Aqui, $A$ é o número de pares de indivíduos adjacentes nas cadeias de parentesco que têm sexos opostos após as alterações; $S$ é a soma das estabilidades das relações reprodutivas após as alterações, isto é, $S=\sum_j s_j$; e $C$ é a soma dos custos das alterações de sexo, isto é, $C=\sum_i c_i$.

Entrada

A entrada é lida do arquivo gender.in.

A primeira linha contém quatro inteiros não negativos $N,K,M,P$: o comprimento das cadeias de parentesco, a quantidade dessas cadeias, o número total de ovinos na amostra e a quantidade de relações reprodutivas, respectivamente.

A segunda linha contém uma string de $M$ caracteres, cada um sendo M ou F, que descreve os sexos iniciais dos $M$ ovinos. M indica macho e F indica fêmea.

A terceira linha contém $M$ inteiros positivos $c_i$, que representam o custo de alterar o sexo de cada ovino.

Cada uma das $K$ linhas seguintes contém $N$ inteiros, que descrevem os números dos ovinos de uma das $K$ cadeias de parentesco. Todos os ovinos são numerados com inteiros de $1$ a $M$. É garantido que os ovinos de cada cadeia têm o mesmo sexo e que as cadeias não se sobrepõem.

Cada uma das $P$ linhas seguintes contém três inteiros positivos $x,y,b$ e um número real $d$, indicando que existe uma relação reprodutiva entre os ovinos $x$ e $y$, com estabilidade inicial $b$ e fator de redução $d$. É garantido que $x$ e $y$ têm sexos iniciais diferentes e pertencem à mesma geração. Cada relação é descrita apenas uma vez nos dados.

Saída

O arquivo de saída gender.out deve conter uma única linha com um inteiro: o maior lucro do plano de alteração.

Exemplos

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

Saída 1

360

Explicação 1

Altere os sexos para MMFFFM. O lucro é $\lfloor10\ln(1+2)\rfloor\times(20+18)-(10+10)=360$.

Temos $A=2$ porque, na cadeia $1-2-3$, os ovinos $2$ e $3$ têm sexos diferentes e, na cadeia $4-5-6$, os ovinos $5$ e $6$ têm sexos diferentes.

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

Saída 2

888

Explicação 2

Altere os sexos para FMFMFMM. O lucro é $\lfloor10\ln(1+4)\rfloor\times(20+18+20)-(10+10+10+10)=888$.

Temos $A=4$ porque, na cadeia $1-2-3$, os ovinos $1$ e $2$ têm sexos diferentes, assim como $2$ e $3$; na cadeia $4-5-6$, os ovinos $4$ e $5$ têm sexos diferentes, assim como $5$ e $6$. Há quatro pares diferentes no total.

Exemplo 3

Veja gender/gender.in e gender/gender.ans no diretório dos participantes.

Restrições

Para 10% dos dados, $M\le 20$.

Para 10% dos dados, $d_j=0$.

Para 10% dos dados, $d_j=0.5$.

Essas três classes de dados são disjuntas duas a duas.

Para 100% dos dados, $N\le 50$, $K\le 4$, $M\le 1000$, $P\le 10000$, $0.0\le d_j\le 1.0$, tanto $b_j$ quanto $c_i$ não excedem $10000$, e $d_j$ tem no máximo 6 casas decimais.