La giuria dell'AMPPZ è composta da cinque persone responsabili di creare una gara interessante ed equilibrata. Quest'anno sono state presentate $n$ proposte di problemi e ne devono essere selezionate $k$. Ogni giurato ordina indipendentemente i problemi in base alla bellezza soggettiva e assegna loro dei punteggi che formano una permutazione* dei numeri da $1$ a $n$. Successivamente la gara seleziona automaticamente i $k$ problemi con il punteggio medio (media aritmetica) più alto. In caso di parità, vengono preferiti i problemi con indici più piccoli.

Quattro giurati hanno già valutato tutti i problemi. L'ultimo è il giurato Jerzy, che segretamente ama la geometria computazionale e vuole che i partecipanti dell'AMPPZ ne sperimentino il più possibile. Per ogni problema sappiamo se è di geometria ($x_i \in \{0, 1\}$) e conosciamo i punteggi degli altri giurati $a_i, b_i, c_i, d_i$. Se Jerzy assegna i suoi punteggi in modo ottimale (anch'essi una permutazione dei numeri da $1$ a $n$), qual è il massimo numero possibile di problemi di geometria selezionati?

*Una sequenza in qualsiasi ordine, senza ripetizioni — ad esempio $(5, 4, 3, 2, 1)$ oppure $(2, 4, 1, 5, 3)$.

Input

La prima riga contiene due interi $n$ e $k$ ($1 \le k \le n \le 200\,000$), che indicano rispettivamente il numero di problemi proposti e il numero di problemi da selezionare per la gara.

Le successive $n$ righe descrivono i problemi proposti; la $i$-esima di esse contiene cinque interi $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$), che descrivono l'$i$-esimo problema. Il valore $x_i$ è uguale a $1$ se il problema è a tema geometrico, e $0$ altrimenti. I quattro numeri successivi sono i punteggi assegnati dagli altri giurati. Ogni giurato ha assegnato $n$ punteggi a due a due distinti, quindi nell'input ogni colonna tranne la prima è una permutazione dei numeri da $1$ a $n$.

Output

Stampa un singolo intero – il massimo numero possibile di problemi di geometria selezionati.

Esempi

Input 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

Output 1

2

Input 2

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

Output 2

1

Note

Nel primo esempio, la giuria seleziona tre dei cinque problemi proposti. I problemi $1$, $3$ e $4$ riguardano la geometria. Jerzy può assegnare i punteggi $(4, 5, 3, 1, 2)$ ai cinque problemi:

1. $x_1 = 1$; media $\frac{3+5+5+2+4}{5} = 3.8$
2. $x_2 = 0$; media $\frac{5+2+4+5+5}{5} = 4.2$
3. $x_3 = 1$; media $\frac{2+3+3+4+3}{5} = 3$
4. $x_4 = 1$; media $\frac{1+1+1+1+1}{5} = 1$
5. $x_5 = 0$; media $\frac{4+4+2+3+2}{5} = 3$

I problemi $1$, $2$ e $3$ verranno selezionati per la gara (i problemi $3$ e $5$ hanno la stessa media, ma il problema $3$ ha l'indice più piccolo). Due dei tre problemi selezionati sono problemi di geometria. Jerzy non può far selezionare più di due problemi di geometria, quindi la risposta è $2$.

Nel secondo esempio, Jerzy non può far selezionare entrambi i problemi di geometria. Entrambi dovrebbero ricevere il punteggio massimo $4$, il che è impossibile perché i punteggi di Jerzy devono essere a due a due distinti.