القرن الحادي والعشرون هو قرن علوم الحياة. تستثمر البشرية موارد بشرية ومادية كبيرة في دراسة علوم الحياة، بهدف التوصل إلى فهم أعمق لآليات بقاء مختلف الكائنات الحية، ومن ثم فهم الإنسان نفسه على نحو أفضل وتحسين جودة الحياة. بدأت حكومة الدولة $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$ منك تصميم خطة لتغيير الجنس تحقق أكبر ربح إجمالي. يحسب الربح كما يلي:

$$\mathit{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$. ويضمن أن جنسيهما الابتدائيين مختلفان وأنهما من الجيل نفسه. توصف كل علاقة في البيانات مرة واحدة فقط.

الإخراج

يحتوي ملف الإخراج 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$ لأن جنسي $2$ و$3$ في سلسلة النسب $1-2-3$ مختلفان، وكذلك جنسا $5$ و$6$ في سلسلة النسب $4-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$ مختلفان وجنسي $2$ و$3$ مختلفان في سلسلة النسب $1-2-3$؛ وجنسي $4$ و$5$ مختلفان وجنسي $5$ و$6$ مختلفان في سلسلة النسب $4-5-6$؛ أي أربعة أزواج مختلفة الجنس إجمالًا.

المثال 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$ على ست.