21 世紀係生命科學嘅世紀。人類投入大量人力物力研究生命科學，希望更深入理解各類生物嘅生存機制，從而更了解人類自己，提高生活質素。Q 國政府首先喺綿羊身上研究性別改造，希望透過基因重組改變性別，增強成個綿羊種群嘅生存能力。如果計劃研究成功，人類就會掌握隨意改變動物性別嘅黑科技，成為生命科學研究史上一個重要里程碑。
Q 國政府揀咗 $M$ 隻綿羊做實驗樣本，當中有 $K$ 條長度為 $N$ 嘅單一性別血緣鏈。「血緣鏈」係由父（母）子（女）關係組成嘅鏈，例如爺爺—爸爸—仔就係一條血緣鏈。「單一性別」即係每條鏈入面所有個體嘅性別都相同，全部係雄性或者全部係雌性。鏈嘅長度係當中個體嘅數量，例如爺爺—爸爸—仔係長度為 3 嘅血緣鏈。呢 $K$ 條鏈互不相交。
留意唔係每隻綿羊都一定屬於某條血緣鏈，有啲可能唔屬於任何鏈，所以 $NK\le M$。除咗血緣鏈，同輩綿羊之間亦可能有「繁衍關係」。兩隻異性綿羊如果曾經繁殖後代，佢哋之間就會有繁衍關係。繁衍關係只會出現喺同輩異性綿羊之間；「同輩」即係輩分相同，綿羊只會同兄弟姊妹輩產生繁衍關係，唔會同父母、子女或者其他更遠輩分嘅綿羊產生呢種關係。
修改綿羊性別需要龐大嘅實驗開支，修改綿羊 $i$ 嘅性別要付出代價 $c_i$。另外，改變性別亦會影響繁衍關係嘅穩定度。每對繁衍關係 $j$ 有初始穩定度 $b_j$ 同衰減係數 $d_j$。所有性別修改完成之後，如果雙方性別都冇改變，穩定度 $s_j=b_j$；如果雙方性別互換，穩定度 $s_j=\lfloor b_jd_j\rfloor$；其他情況下 $s_j=0$。
畀定每隻綿羊嘅性別、修改性別嘅代價、所有血緣鏈同繁衍關係，Q 國政府希望你設計一套性別改造方案，令總收益最大。收益計算如下：
$$Profit=\lfloor10\ln(1+A)\rfloor\cdot S-C.$$
當中 $A$ 係改造後血緣鏈入面相鄰兩隻綿羊性別唔同嘅情況數量；$S$ 係改造後所有繁衍關係穩定度嘅總和，即 $S=\sum_j s_j$；$C$ 係修改綿羊性別嘅代價總和，即 $C=\sum_i c_i$。
輸入格式
輸入檔案係 gender.in。
第一行有四個非負整數 $N,K,M,P$，分別係血緣鏈長度、血緣鏈數量、實驗樣本嘅綿羊總數同繁衍關係數量。
第二行係一個長度為 $M$ 嘅字串，每個字元係 M 或 F，描述呢 $M$ 隻綿羊嘅初始性別。M 代表雄性，F 代表雌性。
第三行有 $M$ 個正整數 $c_i$，表示修改每隻綿羊性別嘅代價。
跟住 $K$ 行，每行有 $N$ 個整數，分別描述呢 $K$ 條血緣鏈入面綿羊嘅編號。所有綿羊用 $1$ 至 $M$ 嘅整數編號。保證每條鏈入面嘅綿羊都係同性，而且各條鏈互不重疊。
跟住 $P$ 行，每行有三個正整數 $x,y,b$ 同一個實數 $d$，表示綿羊 $x$ 同綿羊 $y$ 有繁衍關係，初始穩定度為 $b$，衰減係數為 $d$。保證 $x$ 同 $y$ 初始性別唔同，而且係同輩。同一條關係只會喺資料入面描述一次。
輸出格式
輸出檔案 gender.out 只包含一行一個整數，表示改造計劃嘅最大收益。
樣例
輸入格式 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
輸出格式 1
360
說明 1
將性別改為 MMFFFM。收益係 $\lfloor10\ln(1+2)\rfloor\times(20+18)-(10+10)=360$。
$A=2$ 係因為血緣鏈 $1-2-3$ 入面 $2$ 同 $3$ 嘅性別唔同，而血緣鏈 $4-5-6$ 入面 $5$ 同 $6$ 嘅性別唔同。
輸入格式 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
輸出格式 2
888
說明 2
將性別改為 FMFMFMM。收益係 $\lfloor10\ln(1+4)\rfloor\times(20+18+20)-(10+10+10+10)=888$。
$A=4$ 係因為血緣鏈 $1-2-3$ 入面 $1$ 同 $2$、$2$ 同 $3$ 嘅性別唔同；血緣鏈 $4-5-6$ 入面 $4$ 同 $5$、$5$ 同 $6$ 嘅性別唔同，合共有 4 對。
輸入及輸出 3
見選手目錄下嘅 gender/gender.in 同 gender/gender.ans。
資料範圍
對於 $10\%$ 嘅資料，$M\le20$。
對於 $10\%$ 嘅資料，$d_j=0$。
對於 $10\%$ 嘅資料，$d_j=0.5$。
以上三類資料兩兩冇交集。
對於 $100\%$ 嘅資料，$N\le50$、$K\le4$、$M\le1000$、$P\le10000$、$0.0\le d_j\le1.0$，$b_j$ 同 $c_i$ 都唔大於 $10000$，$d_j$ 小數點後唔超過 6 位。