Disk Optimization

A disk has $N$ sectors numbered $1$ to $N$. A block is any nonempty run of consecutively numbered sectors, and its length is the number of sectors it contains. Two blocks are separate when they share no sector.

Files are stored on the disk. One file may be spread over several sectors that need not form a single block. The content of a file is the concatenation of its sectors read in a fixed order, and inside each block the sectors are read in increasing order of their numbers.

A file's layout is given as a sequence of (start sector, block length) pairs. For example, the sequence

7 3
2 1
5 2

means the file is read from sectors 7, 8, 9, then 2, then 5, 6, in that order.

Every sector is either free or holds part of exactly one file. Files are identified by distinct integers from $1$ to $P$, where $P$ is the number of files.

The disk is optimized when all three conditions hold:

• each file occupies a single block (consecutive sectors),
• a file with a smaller id occupies lower-numbered sectors than every file with a larger id,
• every free sector has a larger number than every occupied sector.

Two operations are allowed:

• copy the content of a block into a separate block of the same length; copying a block of length $t$ takes $t$ microseconds,
• swap the content of two separate blocks of the same length; swapping two blocks of length $t$ takes $2t$ microseconds.

Given the initial layout, compute the minimum total time, in microseconds, needed to bring the disk into the optimized state. If the disk is already optimized, the answer is $0$.

The first line contains two integers: the number of sectors $N$ ($N \le 10000$) and the number of files $P$.

Each file is then described. A file's description begins with a line holding its id (from $1$ to $P$) and the number of separate blocks the file is stored in. The following lines list the blocks, one (start sector, length) pair per line, in the file's read order.

All numbers on a line are separated by single spaces, and the input is guaranteed to be well formed.

Print a single integer: the minimum total time in microseconds required to optimize the disk (print $0$ if it is already optimized).