คณะกรรมการตัดสิน AMPPZ ประกอบด้วยสมาชิกห้าคนซึ่งมีหน้าที่สร้างการแข่งขันที่น่าสนใจและสมดุล ในปีนี้มีข้อเสนอโจทย์ที่ส่งเข้ามา $n$ ข้อ และต้องคัดเลือกไว้ $k$ ข้อ กรรมการแต่ละคนจะเรียงลำดับโจทย์ตามความเจ๋งในมุมมองของตนอย่างเป็นอิสระ และให้คะแนนโจทย์เหล่านั้นเป็นการเรียงสับเปลี่ยน* ของตัวเลขตั้งแต่ $1$ ถึง $n$ จากนั้นระบบการแข่งขันจะคัดเลือกโจทย์ $k$ ข้อที่มีคะแนนเฉลี่ย (ค่าเฉลี่ยเลขคณิต) สูงสุดโดยอัตโนมัติ ในกรณีที่คะแนนเท่ากัน จะเลือกโจทย์ที่มีหมายเลขดัชนีน้อยกว่าก่อน

กรรมการสี่คนได้ให้คะแนนโจทย์ทั้งหมดเรียบร้อยแล้ว คนสุดท้ายคือกรรมการ Jerzy ผู้แอบชื่นชอบเรขาคณิตคำนวณและต้องการให้ผู้เข้าแข่งขัน AMPPZ ได้สัมผัสกับโจทย์ประเภทนี้มากที่สุดเท่าที่จะเป็นไปได้ สำหรับโจทย์แต่ละข้อ เราทราบว่าเป็นโจทย์เรขาคณิตหรือไม่ ($x_i \in \{0, 1\}$) และทราบคะแนนจากกรรมการที่เหลือคือ $a_i, b_i, c_i, d_i$ หาก Jerzy ให้คะแนนของเขาอย่างเหมาะสมที่สุด (ซึ่งเป็นการเรียงสับเปลี่ยนของตัวเลขตั้งแต่ $1$ ถึง $n$ เช่นกัน) จำนวนโจทย์เรขาคณิตที่ได้รับคัดเลือกจะมีได้มากที่สุดกี่ข้อ?

*ลำดับในทิศทางใดก็ได้โดยไม่มีการซ้ำกัน — ตัวอย่างเช่น $(5, 4, 3, 2, 1)$ หรือ $(2, 4, 1, 5, 3)$

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

บรรทัดแรกมีจำนวนเต็มสองตัวคือ $n$ และ $k$ ($1 \le k \le n \le 200\,000$) แทนจำนวนโจทย์ที่ส่งเข้ามาและจำนวนโจทย์ที่จะคัดเลือกสำหรับการแข่งขันตามลำดับ

อีก $n$ บรรทัดถัดไปอธิบายโจทย์ที่ส่งเข้ามา โดยบรรทัดที่ $i$ มีจำนวนเต็มห้าตัวคือ $x_i, a_i, b_i, c_i, d_i$ ($0 \le x_i \le 1$; $1 \le a_i, b_i, c_i, d_i \le n$) อธิบายโจทย์ข้อที่ $i$ ค่า $x_i$ จะเท่ากับ $1$ หากโจทย์ข้อนั้นเป็นหัวข้อเรขาคณิต และเป็น $0$ ในกรณีอื่นๆ ตัวเลขสี่ตัวถัดไปคือคะแนนที่ให้โดยกรรมการคนอื่นๆ กรรมการแต่ละคนให้คะแนนที่แตกต่างกันเป็นคู่ๆ จำนวน $n$ ค่า ดังนั้นในข้อมูลนำเข้าทุกคอลัมน์ยกเว้นคอลัมน์แรกจึงเป็นการเรียงสับเปลี่ยนของตัวเลขตั้งแต่ $1$ ถึง $n$

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

แสดงผลจำนวนเต็มหนึ่งตัว — จำนวนโจทย์เรขาคณิตที่ได้รับคัดเลือกที่มากที่สุดที่เป็นไปได้

ตัวอย่าง

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

5 3
1 3 5 5 2
0 5 2 4 5
1 2 3 3 4
1 1 1 1 1
0 4 4 2 3

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

2

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

4 3
1 1 4 1 2
1 2 3 2 1
0 3 2 3 3
0 4 1 4 4

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

1

หมายเหตุ

ในตัวอย่างแรก คณะกรรมการคัดเลือกโจทย์สามข้อจากที่ส่งเข้ามาห้าข้อ โจทย์ข้อ $1$, $3$ และ $4$ เกี่ยวกับเรขาคณิต Jerzy สามารถให้คะแนน $(4, 5, 3, 1, 2)$ แก่โจทย์ทั้งห้าข้อได้ดังนี้:

1. $x_1 = 1$; ค่าเฉลี่ย $\frac{3+5+5+2+4}{5} = 3.8$
2. $x_2 = 0$; ค่าเฉลี่ย $\frac{5+2+4+5+5}{5} = 4.2$
3. $x_3 = 1$; ค่าเฉลี่ย $\frac{2+3+3+4+3}{5} = 3$
4. $x_4 = 1$; ค่าเฉลี่ย $\frac{1+1+1+1+1}{5} = 1$
5. $x_5 = 0$; ค่าเฉลี่ย $\frac{4+4+2+3+2}{5} = 3$

โจทย์ข้อ $1$, $2$ และ $3$ จะได้รับคัดเลือกสำหรับการแข่งขัน (โจทย์ข้อ $3$ และ $5$ มีค่าเฉลี่ยเท่ากัน แต่โจทย์ข้อ $3$ มีดัชนีน้อยกว่า) โจทย์สองในสามข้อที่ได้รับคัดเลือกเป็นโจทย์เรขาคณิต Jerzy ไม่สามารถทำให้โจทย์เรขาคณิตได้รับคัดเลือกมากกว่าสองข้อได้ ดังนั้นคำตอบคือ $2$

ในตัวอย่างที่สอง Jerzy ไม่สามารถทำให้โจทย์เรขาคณิตทั้งสองข้อได้รับคัดเลือกพร้อมกันได้ เพราะทั้งสองข้อจะต้องได้รับคะแนนสูงสุดคือ $4$ เหมือนกัน ซึ่งเป็นไปไม่ได้เนื่องจากคะแนนของ Jerzy ต้องแตกต่างกันทั้งหมด