The AMPPZ jury consists of five people who are responsible for creating an interesting and balanced contest. This year, $n$ problem proposals were submitted and $k$ of them must be selected. Each juror independently orders the problems by subjective coolness and assigns them scores that form a permutation* of the numbers from $1$ to $n$. Then the contest automatically selects the $k$ problems with the highest average score (arithmetic mean). In case of ties, problems with smaller indices are preferred.

Four jurors have already graded all the problems. The last one is juror Jerzy, who secretly likes computational geometry and wants AMPPZ participants to experience as much of it as possible. For each problem, we know whether it is geometry ($x_i \in \{0, 1\}$), and we know the scores from the remaining jurors $a_i, b_i, c_i, d_i$. If Jerzy assigns his scores optimally (also a permutation of the numbers from $1$ to $n$), what is the maximum possible number of selected geometry problems?

*A sequence in any order, without repetitions — for example $(5, 4, 3, 2, 1)$ or $(2, 4, 1, 5, 3)$.

Input

The first line contains two integers $n$ and $k$ ($1 \le k \le n \le 200\,000$), denoting respectively the number of submitted problems and the number of problems to be selected for the contest.

The next $n$ lines describe the submitted problems; the $i$-th of them contains five integers $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$), describing the $i$-th problem. The value $x_i$ is equal to $1$ if the problem is geometry-themed, and $0$ otherwise. The next four numbers are the scores given by the remaining jurors. Each juror assigned $n$ pairwise distinct scores, so in the input each column except the first is a permutation of the numbers from $1$ to $n$.

Output

Output a single integer – the maximum possible number of selected geometry problems.

Examples

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

In the first example, the jury selects three of the five submitted problems. Problems $1$, $3$, and $4$ are about geometry. Jerzy can assign the scores $(4, 5, 3, 1, 2)$ to the five problems:

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

Problems $1$, $2$, and $3$ will be selected for the contest (problems $3$ and $5$ have the same average, but problem $3$ has the smaller index). Two of the three selected problems are geometry problems. Jerzy cannot get more than two geometry problems selected, so the answer is $2$.

In the second example, Jerzy cannot get both geometry problems selected. They would both have to receive the highest score $4$, which is impossible because Jerzy's scores must be pairwise distinct.