คำอธิบายโจทย์

Xiao Bo เป็นนักศึกษามหาวิทยาลัยที่ขยันขันแข็งและให้ความสำคัญกับผลการเรียนของตนเองเป็นอย่างมาก ในแต่ละภาคการศึกษา เขาจะได้รับหน่วยกิตและแต้มระดับคะแนนที่สอดคล้องกันสำหรับหลายรายวิชา แต้มระดับคะแนนเป็นวิธีวัดผลการเรียนของรายวิชา ในขณะที่เกรดเฉลี่ยสะสม (GPA) เป็นตัวชี้วัดที่สำคัญของระดับวิชาการโดยรวมของนักศึกษา Xiao Bo หวังว่าจะทำ GPA ให้ได้สูงที่สุดเท่าที่จะเป็นไปได้

ทางมหาวิทยาลัยมีนโยบายพิเศษ คือ ในแต่ละภาคการศึกษา นักศึกษาสามารถเลือกเปลี่ยนผลการเรียนของรายวิชาเป็นโหมด "ผ่าน/ไม่ผ่าน" (Pass/No Pass - PNP) ได้ไม่เกินหนึ่งวิชา (แน่นอนว่าพวกเขาสามารถเลือกที่จะไม่เปลี่ยนรายวิชาใดเลยเป็นโหมด PNP ในบางภาคการศึกษาก็ได้) ในโหมด PNP แต้มระดับคะแนนของรายวิชานี้จะไม่ถูกนำมารวมในการคำนวณ GPA

Xiao Bo ทราบว่าเขาได้ลงทะเบียนเรียนไปทั้งหมด $n$ รายวิชาตลอด $m$ ภาคการศึกษา เขาทราบหน่วยกิต แต้มระดับคะแนน และภาคการศึกษาของแต่ละรายวิชาในใบแสดงผลการเรียน ซึ่งแทนด้วย $s_i, g_i, t_i$ รับประกันว่า $2m$ รายวิชาแรกในใบแสดงผลการเรียนเป็นไปตามเงื่อนไขที่ว่า ภาคการศึกษาของรายวิชาที่ $i$ คือ $\lfloor \frac{i+1}{2} \rfloor$ (สิ่งนี้รับประกันว่าในแต่ละภาคการศึกษาจะมีการเรียนอย่างน้อยสองรายวิชา) ในขณะที่ภาคการศึกษาของรายวิชาที่เหลือไม่ได้มีการรับประกันรูปแบบดังกล่าว Xiao Bo หวังว่าจะตัดสินใจอย่างเหมาะสมในแต่ละภาคการศึกษาเพื่อให้ได้ GPA สุดท้ายสูงที่สุด

อย่างไรก็ตาม Xiao Bo คิดว่าปัญหานี้ง่ายเกินไปสักหน่อยและต้องการทราบว่า สำหรับทุกค่า $k$ ที่สอดคล้องกับ $2m \le k \le n$ หากเขาเรียนเฉพาะรายวิชาตั้งแต่ลำดับที่ $1$ ถึงลำดับที่ $k$ ในใบแสดงผลการเรียน เมื่อพิจารณาการตัดสินใจเลือก PNP ในแต่ละภาคการศึกษาแล้ว เขาจะสามารถทำ GPA สูงสุดได้เท่าใด?

สูตรการคำนวณ GPA มีดังนี้: สมมติว่าปัจจุบันมี $n$ รายวิชาที่ไม่ได้เลือกโหมด PNP โดยที่รายวิชาที่ $i$ มีหน่วยกิตและแต้มระดับคะแนนเป็น $s_i, g_i$ ตามลำดับ แล้ว

$$\text{GPA} = \frac{\sum_{i=1}^n s_i \cdot g_i}{\sum_{i=1}^n s_i}$$

ข้อมูลนำเข้า

มีหลายชุดทดสอบในไฟล์เดียว บรรทัดแรกของข้อมูลนำเข้าประกอบด้วยจำนวนเต็มหนึ่งจำนวน $T$ ($1 \le T \le 10^4$) แทนจำนวนชุดทดสอบ

สำหรับแต่ละชุดทดสอบ:

• บรรทัดแรกประกอบด้วยจำนวนเต็มบวกสองจำนวน $n, m$ ($1 \le m \le 8, 2m \le n \le 10^5$) คั่นด้วยช่องว่าง แทนจำนวนรายวิชาทั้งหมดและจำนวนภาคการศึกษาตามลำดับ
• อีก $n$ บรรทัดถัดมา แต่ละบรรทัดประกอบด้วยจำนวนเต็มสามจำนวน $s_i, g_i, t_i$ ($1 \le s_i, g_i \le 10^5, 1 \le t_i \le m$) คั่นด้วยช่องว่าง แทนหน่วยกิต แต้มระดับคะแนน และภาคการศึกษาที่เรียนรายวิชานั้นตามลำดับ รับประกันว่า $\forall 1 \le i \le 2m, t_i = \lfloor \frac{i+1}{2} \rfloor$

รับประกันว่าผลรวมของ $n$ ในทุกชุดทดสอบไม่เกิน $3 \times 10^5$ กล่าวคือ $\sum n \le 3 \times 10^5$

ข้อมูลส่งออก

สำหรับแต่ละชุดทดสอบ ให้แสดงผล $n - 2m + 1$ บรรทัด โดยแต่ละบรรทัดสอดคล้องกับ $k = 2m, k = 2m+1, \dots, k = n$ แทนค่า GPA สูงสุดที่ Xiao Bo สามารถทำได้หากเขาเรียนเฉพาะรายวิชาตั้งแต่ลำดับที่ $1$ ถึงลำดับที่ $k$ ในใบแสดงผลการเรียน

ข้อกำหนดความแม่นยำของคำตอบ: ข้อมูลส่งออกของคุณจะถูกนำไปเปรียบเทียบกับคำตอบมาตรฐาน หากค่าที่ผู้เข้าแข่งขันแสดงผลคือ $x$ และคำตอบมาตรฐานคือ $y$ จะถือว่าถูกต้องเมื่อ $\frac{|x-y|}{\max(1,|y|)} \le 10^{-6}$

ตัวอย่าง

ตัวอย่าง 1

2
5 1
9 7 1
1 2 1
9 6 1
6 4 1
4 7 1
9 2
9 1 1
9 9 1
1 9 2
4 4 2
6 10 1
8 6 2
2 7 1
8 6 2
6 5 1

7.0000000000
6.5000000000
6.2631578947
6.3913043478
9.0000000000
9.3750000000
8.3000000000
8.1818181818
7.6470588235
7.2500000000