21 世紀是生命科學的世紀。人類投入大量人力物力研究生命科學，旨在對各類生物的生存機理產生更加深入的理解，以更好地了解人類自身，提高生活品質。Q 國政府首先在綿羊中開展了性別改造的研究，希望透過基因重組改變性別的方式增強整個綿羊種群的生存能力。若此計畫能夠順利研究成功，人類將掌握隨意改變動物性別的黑科技，這將是生命科學研究史上的一個重要里程碑。

Q 國政府從綿羊群中挑選出 $M$ 隻綿羊作為實驗樣本，這 $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=\lfloor 10\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$ 的初始性別不同，$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

說明

改性別為 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

說明

改性別為 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$。