21世紀は生命科学の世紀です。人類はさまざまな生物の生存の仕組みをより深く理解し、それによって人類自身への理解を深め、生活の質を向上させるために、多大な人的・物的資源を生命科学の研究に投入しています。Q国政府はまずヒツジを対象に性別変更の研究を始め、遺伝子の組換えによって性別を変えることで、ヒツジの個体群全体の生存能力を高めようとしています。この研究計画が成功すれば、人類は動物の性別を自由に変える驚異的な技術を手に入れることになります。これは生命科学研究の歴史における重要な節目となるでしょう。
Q国政府は実験用の標本として $M$ 頭のヒツジを選びました。この $M$ 頭には、長さ $N$ の単一性別の血縁鎖が $K$ 本存在します。「血縁鎖」とは、父（母）と子の関係で結ばれた鎖のことです。例えば、祖父―父―息子は1本の血縁鎖です。「単一性別」とは、各血縁鎖に属するすべての個体が同じ性別であり、すべてオスか、すべてメスであることを意味します。血縁鎖の長さは、鎖に含まれる個体の数です。例えば、祖父―父―息子は長さ3の血縁鎖です。この $K$ 本の血縁鎖は互いに交わりません。
すべてのヒツジが血縁鎖に属する必要はなく、どの血縁鎖にも属さないヒツジもいることに注意してください。したがって $NK\le M$ です。血縁鎖以外にも、同世代のヒツジの間には「繁殖関係」があります。異なる性別の2頭のヒツジが過去に子をもうけたことがあれば、その2頭の間に繁殖関係が生じます。繁殖関係は同世代の異性の個体間にしか存在しません。ここで「同世代」とは世代が同じことを意味し、ヒツジは兄弟姉妹と同じ世代の個体とのみ繁殖関係を持ち、親や子、あるいはさらに離れた世代の個体とは繁殖関係を持ちません。
ヒツジの性別を変更する実験には多額の費用がかかり、ヒツジ $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$ は変更後の血縁鎖において隣り合う2頭の性別が異なる箇所の数、$S$ は変更後の繁殖関係の安定度の合計、すなわち $S=\sum_j s_j$、$C$ はヒツジの性別変更にかかる費用の合計、すなわち $C=\sum_i c_i$ です。
入力
最初の行には4個の非負整数 $N,K,M,P$ が与えられ、それぞれ血縁鎖の長さ、血縁鎖の本数、実験標本のヒツジの総数、繁殖関係の数を表します。
2行目には、各文字が M または F である長さ $M$ の文字列が与えられ、$M$ 頭のヒツジの初期の性別を表します。M はオス、F はメスを表します。
3行目には $M$ 個の正整数 $c_i$ が与えられ、各ヒツジの性別変更の費用を表します。
続く $K$ 行にはそれぞれ $N$ 個の整数が与えられ、$K$ 本の血縁鎖に属するヒツジの番号を表します。すべてのヒツジには $1$ から $M$ の整数で番号が付いています。各鎖に属するヒツジはすべて同性であり、鎖どうしは重ならないことが保証されます。
続く $P$ 行にはそれぞれ3個の正整数 $x,y,b$ と1個の実数 $d$ が与えられます。これはヒツジ $x$ とヒツジ $y$ の間に繁殖関係があり、その初期安定度が $b$、減衰係数が $d$ であることを表します。$x$ と $y$ の初期の性別は異なり、同世代であることが保証されます。同じ関係がデータ中に記述されるのは1回だけです。
出力
1行に1個の整数として、変更計画の最大利益を出力してください。
入出力例
入力 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$ を満たします。
上記の3種類のデータは互いに重なりません。
すべてのデータで $N\le50$、$K\le4$、$M\le1000$、$P\le10000$、$0.0\le d_j\le1.0$ を満たし、$b_j$ と $c_i$ はともに $10000$ 以下で、$d_j$ の小数点以下の桁数は6以下です。