تتكون لجنة تحكيم AMPPZ من خمسة أشخاص مسؤولين عن إعداد مسابقة ممتعة ومتوازنة. هذا العام، تم تقديم $n$ من مقترحات المسائل ويجب اختيار $k$ منها. يقوم كل حَكَم بشكل مستقل بترتيب المسائل حسب روعتها الذاتية ويمنحها درجات تشكل تبديلاً* للأعداد من $1$ إلى $n$. بعد ذلك، تختار المسابقة تلقائياً المسائل الـ $k$ ذات أعلى متوسط درجات (المتوسط الحسابي). في حالة التعادل، تُفضَّل المسائل ذات الفهارس الأصغر.

لقد قام أربعة حكام بالفعل بتقييم جميع المسائل. الحَكَم الأخير هو جيرزي، الذي يحب سراً الهندسة الحسابية ويريد أن يختبرها مشاركو AMPPZ قدر الإمكان. لكل مسألة، نعلم ما إذا كانت هندسية ($x_i \in \{0, 1\}$)، ونعلم الدرجات التي منحها بقية الحكام $a_i, b_i, c_i, d_i$. إذا قام جيرزي بتوزيع درجاته بشكل مثالي (وهي أيضاً تبديل للأعداد من $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$ تتعلق بالهندسة. يمكن لجيرزي إعطاء الدرجات $(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$ لها فهرس أصغر). اثنتان من المسائل الثلاث المختارة هما مسألتان هندسيتان. لا يستطيع جيرزي جعل أكثر من مسألتين هندسيتين تُختاران، لذا فإن الإجابة هي $2$.

في المثال الثاني، لا يستطيع جيرزي جعل كلتا المسألتين الهندسيتين تُختاران. إذ سيتعين على كلتيهما الحصول على الدرجة القصوى $4$، وهو أمر مستحيل لأن درجات جيرزي يجب أن تكون مختلفة مثنى مثنى.