Description

For maximum security, the headquarters uses a special secure operating system with a special file system. In this file system, all disk space is divided into $N$ blocks of equal size, labeled with integers $1$ to $N$. Each file occupies one or more blocks located in arbitrary regions of the disk, and blocks not occupied by any file are considered available. If a file is stored in physically contiguous blocks on the disk, it can be read at the highest speed.

Because the disk rotates at a constant speed, the time needed to access different blocks varies. Reading blocks near the beginning of the disk is faster than reading blocks near the end. Based on this, files are pre-labeled by their access frequency with integers $1$ to $K$. In the optimal placement on the disk, file $1$ occupies blocks $1, 2, \cdots, S_1$, file $2$ occupies blocks $S_1 + 1, S_1 + 2, \cdots, S_1 + S_2$, and so on (where $S_i$ is the number of blocks occupied by file $i$). To store files in their optimal form, block move operations may be performed. One block move operation consists of reading an occupied block from the disk into memory and writing it to some other empty block, then marking the former block free and the latter block occupied.

The goal is to store the files in the optimal way using the minimum number of block move operations. Note that the relative order of the blocks within the same file must not change after moving.

Input Format

Each disk description starts with a line containing two integers $N$ and $K$ ($1 \le K \le N \le 10^5$). The next $K$ lines each describe one file. For file $i$, the description begins with an integer $S_i$, the number of blocks of this file ($1 \le S_i \le N - K$), followed by $S_i$ integers separated by spaces, giving the block IDs that the file currently occupies on the disk in natural order. All these numbers are between $1$ and $N$, inclusive. Within one disk description, all occupied block IDs are distinct, and there is at least one empty block.

There may be multiple disk descriptions; process all of them until EOF.

Output Format

For each disk description, output a single line $\text{``\texttt{We need \textrm{\textit{M}} move operations.}''}$, where $M$ is the minimum number of block move operations required to store the files in the optimal way. If the files are already in the optimal placement, output $\text{``\texttt{No optimization needed.}''}$.

20 3
4 2 3 11 12
1 7
3 18 5 10

We need 9 move operations.

Hint

Translated by ChatGPT 5