המאה ה־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=\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$ מספרים שלמים, המתארים את מספרי הכבשים בשרשרת היוחסין המתאימה. כל הכבשים ממוספרות במספרים שלמים מ־$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 ספרות אחרי הנקודה העשרונית.