题目描述

21 世纪是生命科学的世纪。人类投入了大量人力物力研究生命科学，旨在对各类生物的生存机理产生更加深入的理解，以更好地了解人类自身，提高生活质量。Q 国政府首先在绵羊中开展了性别改造研究，希望通过基因重组改变性别的方式增强整个绵羊种群的生存能力。若此计划能够顺利研究成功，人类将掌握随意改变动物性别的黑科技，这将是生命科学研究史上一个重要的里程碑。

Q 国政府从绵羊群中挑出 \(M\) 只绵羊作为实验样本，这 \(M\) 只绵羊中存在 \(K\) 条长度为 \(N\) 的单一性别的血缘链。所谓 “血缘链” 是指的一条由父（母）子（女）关系组成的链，比如 “爷爷 - 爸爸 - 儿子” 就是一条血缘链。“单一性别” 的意思是每条血缘链中所有个体的性别均一致，同为雄性或同为雌性。血缘链长度指的是一条血缘链中个体的数量，比如 “爷爷 - 爸爸 - 儿子” 是一条长度为 \(3\) 的血缘链。这 \(K\) 条血缘链并不相交。

注意并不是每只绵羊都必须属于一条血缘链，有些绵羊可能不属于任何血缘链，因此 \(N\times K\leq M\)。除去血缘链外，同辈绵羊还会有 “繁衍关系” 的存在。两只异性绵羊如果曾经繁殖过后代，那么它们之间就会产生 “繁衍关系”。注意繁衍关系只会出现在同辈异性绵羊个体之间，这里 “同辈” 表示两只绵羊的辈份相同，即绵羊只会与它的兄弟姐妹辈产生 “繁衍关系”，而不会与父母或子女或其他更远的辈份之间产生 “繁衍关系”。

对绵羊进行性别修改需要花费巨大的实验开销，修改绵羊 \(i\) 的性别需要花费 \(c_i\) 的修改代价。除此以外，修改绵羊性别还会对繁衍关系的稳定度产生影响：每对繁衍关系 \(j\) 有初始稳定度 \(b_j\) 和衰减系数 \(d_j\)，当所有的性别修改操作完成后，若双方性别均未改变，则此关系稳定度 \(s_j = b_j\)，若双方性别互换，则稳定度 \(s_j = \lfloor b_jd_j\rfloor\)，其他情况下稳定度 \(s_j = 0\)。

给定每只绵羊的性别，性别修改代价，所有血缘链关系很繁衍关系，Q 国政府希望你来设计一套性别改造方案，使总收益最大。收益计算方式如下：

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

其中 \(A\) 为改造后血缘链相邻两者为异性的情况数量，\(S\) 为改造后繁衍关系稳定度之和，即 \(S = \sum\limits_js_j\)，\(C\) 为修改绵羊性别带来的代价之和，即 \(C = \sum\limits_ic_i\)。

输入

第一行，包含四个非负整数 \(N,K,M,P\)，分别为血缘链的长度，血缘链的数量，实验样本中的总绵羊和繁衍关系的数量。

第二行，为一个 \(M\) 个字符的字符串，每个字符为 M 或 F，描述了这 \(M\) 只绵羊的初始性别。M 表示雄性，F 表示雌性。

第三行，\(M\) 个正整数，表示修改每只绵羊性别的代价。

下面 \(K\) 行每行 \(N\) 个整数，分别描述这 \(K\) 个血缘链中绵羊编号（所有绵羊用 1 到 \(M\) 的整数编号），保证每条链中的绵羊均为同性，且链互不交叠。

下面 \(P\) 行每行三个正整数 \(x,y,b\) 和一个实数 \(d\)，表示绵羊 \(x\) 与绵羊 \(y\) 存在繁衍关系，且其初始关系稳定度为 \(b\)，衰减系数为 \(d\)。

保证 \(x\) 与 \(y\) 的初始性别不同，\(x\) 和 \(y\) 为同辈。同一条关系只会在数据中描述一次。

输出

一个整数，表示改造计划的最大收益。

样例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

输出

360

解释

改性别为 MMFFFM。收益为 \(\lfloor 10 \ln(1 + 2) \rfloor \times(20 + 18) - (10 + 10) = 360\)。\(A = 2\) 是因为血缘链 \(1 - 2 - 3\) 中 \(2\) 与 \(3\) 性别的不同，血缘链 \(4 - 5 - 6\) 中 \(5\) 与 \(6\) 的性别不同。

数据范围限制

对于 \(10\%\) 的数据，满足 \(M \leq 20\)；

对于 \(10\%\) 的数据，满足 \(d_j=0\)；

对于 \(10\%\) 的数据，满足 \(d_j=0.5\)；

上述三类数据两两没有交集。

对于 \(100\%\) 的数据，\(N \leq 50\)，\(K \leq 4\)，\(M \leq 10^3\)，\(P \leq 10^4\)，\(0.0 \leq d_j \leq 1.0\)，\(b_j\) 和 \(c_i\) 均不大于 \(10^4\)，\(d_j\) 的小数位数不超过 6。

限制

每个测试点时限：5秒
内存限制：2GB