XXI століття — століття наук про життя. Людство вкладає великі людські й матеріальні ресурси в дослідження механізмів існування різних організмів, щоб краще зрозуміти себе та підвищити якість життя. Уряд країни 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 означає самця, F — самицю.
Третій рядок містить $M$ додатних цілих чисел $c_i$ — вартості зміни статі кожної вівці.
Наступні $K$ рядків містять по $N$ цілих чисел — номери овець у відповідних ланцюжках. Усі вівці пронумеровані цілими числами від $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 цифр після десяткової крапки.