Журі 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$, що неможливо, оскільки оцінки Єжи мають бути попарно різними.