Le jury de l'AMPPZ est composé de cinq personnes chargées de créer un concours intéressant et équilibré. Cette année, $n$ propositions de problèmes ont été soumises et $k$ d'entre elles doivent être sélectionnées. Chaque membre du jury classe indépendamment les problèmes selon leur intérêt subjectif et leur attribue des notes formant une permutation* des nombres de $1$ à $n$. Ensuite, le concours sélectionne automatiquement les $k$ problèmes ayant la note moyenne (moyenne arithmétique) la plus élevée. En cas d'égalité, les problèmes ayant les plus petits indices sont privilégiés.

Quatre membres du jury ont déjà noté tous les problèmes. Le dernier est Jerzy, qui aime secrètement la géométrie algorithmique et souhaite que les participants de l'AMPPZ en fassent l'expérience autant que possible. Pour chaque problème, nous savons s'il s'agit de géométrie ($x_i \in \{0, 1\}$), et nous connaissons les notes des autres membres du jury $a_i, b_i, c_i, d_i$. Si Jerzy attribue ses notes de manière optimale (également une permutation des nombres de $1$ à $n$), quel est le nombre maximum possible de problèmes de géométrie sélectionnés ?

*Une suite dans un ordre quelconque, sans répétition — par exemple $(5, 4, 3, 2, 1)$ ou $(2, 4, 1, 5, 3)$.

Entrée

La première ligne contient deux entiers $n$ et $k$ ($1 \le k \le n \le 200\,000$), désignant respectivement le nombre de problèmes soumis et le nombre de problèmes à sélectionner pour le concours.

Les $n$ lignes suivantes décrivent les problèmes soumis ; la $i$-ème d'entre elles contient cinq entiers $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$), décrivant le $i$-ème problème. La valeur $x_i$ est égale à $1$ si le problème porte sur la géométrie, et à $0$ sinon. Les quatre nombres suivants sont les notes attribuées par les autres membres du jury. Chaque membre du jury ayant attribué $n$ notes deux à deux distinctes, chaque colonne de l'entrée à l'exception de la première est une permutation des nombres de $1$ à $n$.

Sortie

Affichez un seul entier – le nombre maximum possible de problèmes de géométrie sélectionnés.

Exemples

Entrée 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

Sortie 1

2

Entrée 2

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

Sortie 2

1

Note

Dans le premier exemple, le jury sélectionne trois des cinq problèmes soumis. Les problèmes $1$, $3$ et $4$ portent sur la géométrie. Jerzy peut attribuer les notes $(4, 5, 3, 1, 2)$ aux cinq problèmes :

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

Les problèmes $1$, $2$ et $3$ seront sélectionnés pour le concours (les problèmes $3$ et $5$ ont la même moyenne, mais le problème $3$ a un indice plus petit). Deux des trois problèmes sélectionnés sont des problèmes de géométrie. Jerzy ne peut pas faire sélectionner plus de deux problèmes de géométrie, la réponse est donc $2$.

Dans le deuxième exemple, Jerzy ne peut pas faire sélectionner les deux problèmes de géométrie. Ils devraient tous deux recevoir la note maximale $4$, ce qui est impossible car les notes de Jerzy doivent être deux à deux distinctes.