Unstacking Boxes

A boy has just moved house. Before the move he packed all of his books into numbered boxes, and he wrote an inventory saying which box each book went into. He put that inventory in box 1.

In his new room he found that his parents had stacked the boxes into several piles standing in a row, with each pile touching the next one.

The boy is methodical, so he wants the inventory back before he opens any other box. He is also clumsy. To pull a box out of a pile, the box has to be on top of its pile and at least one of its two sides has to be free, which means no box touches it on that side. Either side will do.

Consider the box sitting at position $h$ from the bottom of the $i$-th pile from the left. Its left side is blocked if pile $i-1$ holds $h$ or more boxes at that moment, and free otherwise. The right side works the same way with pile $i+1$. Nothing stands to the left of the first pile or to the right of the last pile, so those sides are always free.

The room is large, so the boy puts every box he takes out somewhere else without disturbing the piles his parents built.

Given the positions of the boxes in the piles, find the smallest number of boxes, box 1 excluded, that the boy has to take out in order to get box 1.

The input holds several test cases. The first line of each test case has two integers $N$ and $P$, the number of boxes and the number of piles ($1 \le P \le N \le 1000$). The boxes are numbered from 1 to $N$.

Each of the next $P$ lines describes one pile, in left to right order. The $i$-th of those lines starts with an integer $Q_i$, the number of boxes in pile $i$, then a single blank, then $Q_i$ box numbers separated by blanks. The numbers are listed from the bottom of the pile to its top.

Every pile holds at least one box, and every box appears exactly once in the whole input. All boxes have the same shape and size.

A line with $N$ and $P$ both equal to 0 marks the end of the input. That line is not a test case.

For each test case print one line with a single integer: the smallest number of boxes, box 1 excluded, that the boy has to take out to get box 1.