ศตวรรษที่ 21 เป็นศตวรรษแห่งวิทยาศาสตร์ชีวภาพ มนุษย์ทุ่มเทกำลังคนและทรัพยากรเพื่อศึกษากลไกการดำรงชีวิตของสิ่งมีชีวิตให้ลึกซึ้งยิ่งขึ้น เพื่อเข้าใจตนเองและยกระดับคุณภาพชีวิต รัฐบาลประเทศ 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$ ตัว โดย M แทนเพศผู้ และ F แทนเพศเมีย

บรรทัดที่สามประกอบด้วยจำนวนเต็มบวก $c_i$ จำนวน $M$ จำนวน แทนค่าใช้จ่ายในการเปลี่ยนเพศแกะแต่ละตัว

จากนั้นมี $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 ตำแหน่ง