Жюри 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$, что невозможно, так как оценки Ежи должны быть попарно различны.