A great scientific conference is being organized in Byteotia, lasting $k$ days. Every day, a certain number of meetings take place in parallel (at the same time). Furthermore, some meetings are continuations of meetings that took place the previous day.

A participant can attend at most one meeting per day. Additionally, if meeting $b$ is a continuation of meeting $a$, a participant can attend meeting $b$ only if they attended meeting $a$ the previous day. A meeting can be a continuation of at most one meeting from the previous day, but multiple meetings can be a continuation of the same meeting (its participants split into groups the next day, and some may not go to any continuation).

The King of Byteotia wants to know exactly what will happen at every meeting, so he has decided to send his trusted employees to the conference. Help him determine the minimum number of employees he must send so that at least one of them can attend every meeting.

Input

The first line of input contains two positive integers $k$ and $n_1$ ($1 \le k, n_1 \le 500\,000$), representing the number of days of the conference and the number of meetings taking place on the first day, respectively (since it is the first day, no meeting can be a continuation of an earlier meeting).

Then, if $k > 1$, for $2 \le i \le k$, the $i$-th line contains the description of day $i$. It starts with a positive integer $n_i$ ($1 \le n_i \le 500\,000$), representing the number of meetings taking place on the $i$-th day, followed by a sequence of $n_i$ integers $a_{i,1}, \dots, a_{i,n_i}$ ($0 \le a_{i,j} \le n_{i-1}$). The value $a_{i,j} = 0$ means that the $j$-th meeting of the $i$-th day is not a continuation of any earlier meeting; if $a_{i,j} > 0$, then the $j$-th meeting of the $i$-th day is a continuation of the $a_{i,j}$-th meeting from day $i-1$.

Meetings on each day are numbered from $1$ to $n_i$. The total number of meetings, i.e., the sum of all $n_i$, is no greater than $500\,000$.

Output

Output a single integer – the minimum number of employees that must be sent to the conference so that at least one of them can attend every meeting.

Examples

Input 1

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

Output 1

6

Note

We send six employees to the conference, let's call them A, B, C, D, E, and F. On the first day, we send employees A, B, C, and D to the first meeting, employee E to the second, and employee F to the third. On the second day, E and F stay home (there is no meeting they could attend), employees A and B go to the second meeting, and C and D go to the first and third meetings. On the third day, A and B go to the third meeting; and for the remaining meetings, we send one of the other employees to each. Finally, on the last day, A and B go to the first and second meetings. It can be seen that five employees are not enough to visit all meetings.