XXI век — век наук о жизни. Человечество вкладывает огромные людские и материальные ресурсы в их изучение, стремясь глубже понять механизмы существования различных организмов, лучше узнать самих себя и повысить качество жизни. Правительство страны 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=\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
Примечание
После изменений пол овец задаётся строкой 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 цифр после десятичной точки.