חבר השופטים של 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$, דבר שאינו אפשרי מכיוון שהציונים של יז'י חייבים להיות שונים זה מזה.