Jury AMPPZ składa się z pięciu osób odpowiedzialnych za stworzenie ciekawego i zrównoważonego konkursu. W tym roku zgłoszono $n$ propozycji zadań, spośród których należy wybrać $k$. Każdy juror niezależnie porządkuje zadania według subiektywnej fajności i przyznaje im oceny tworzące permutację* liczb od $1$ do $n$. Następnie na zawody automatycznie wybieranych jest $k$ zadań o najwyższej średniej ocenie (średniej arytmetycznej). W przypadku remisów preferowane są zadania o mniejszych numerach.

Czterech jurorów oceniło już wszystkie zadania. Ostatnim jest juror Jerzy, który skrycie lubi geometrię obliczeniową i chce, aby uczestnicy AMPPZ doświadczyli jej jak najwięcej. Dla każdego zadania wiemy, czy jest ono geometryczne ($x_i \in \{0, 1\}$), oraz znamy oceny pozostałych jurorów $a_i, b_i, c_i, d_i$. Jeśli Jerzy przyzna swoje oceny optymalnie (również permutację liczb od $1$ do $n$), to jaka jest maksymalna możliwa liczba wybranych zadań geometrycznych?

*Ciąg w dowolnej kolejności, bez powtórzeń — na przykład $(5, 4, 3, 2, 1)$ lub $(2, 4, 1, 5, 3)$.

Wejście

Pierwszy wiersz zawiera dwie liczby całkowite $n$ oraz $k$ ($1 \le k \le n \le 200\,000$), oznaczające odpowiednio liczbę zgłoszonych zadań oraz liczbę zadań, które mają zostać wybrane na zawody.

Kolejne $n$ wierszy opisuje zgłoszone zadania; $i$-ty z nich zawiera pięć liczb całkowitych $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$), opisujących $i$-te zadanie. Wartość $x_i$ jest równa $1$, jeśli zadanie ma tematykę geometryczną, a $0$ w przeciwnym razie. Kolejne cztery liczby to oceny przyznane przez pozostałych jurorów. Każdy juror przyznał $n$ parami różnych ocen, więc na wejściu każda kolumna oprócz pierwszej jest permutacją liczb od $1$ do $n$.

Wyjście

Wypisz jedną liczbę całkowitą – maksymalną możliwą liczbę wybranych zadań geometrycznych.

Przykłady

Wejście 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

Wyjście 1

2

Wejście 2

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

Wyjście 2

1

Uwaga

W pierwszym przykładzie jury wybiera trzy z pięciu zgłoszonych zadań. Zadania $1$, $3$ i $4$ dotyczą geometrii. Jerzy może przyznać pięciu zadaniom oceny $(4, 5, 3, 1, 2)$:

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

Na zawody zostaną wybrane zadania $1$, $2$ i $3$ (zadania $3$ i $5$ mają taką samą średnią, ale zadanie $3$ ma mniejszy numer). Dwa z trzech wybranych zadań są zadaniami geometrycznymi. Jerzy nie może doprowadzić do wybrania więcej niż dwóch zadań geometrycznych, więc odpowiedzią jest $2$.

W drugim przykładzie Jerzy nie może doprowadzić do wybrania obu zadań geometrycznych. Oba musiałyby otrzymać najwyższą ocenę $4$, co jest niemożliwe, ponieważ oceny Jerzego muszą być parami różne.