Lasers

Time limit1sMemory limit512 MB

Summary

Each row holds sliding walls of fixed widths; count laser positions blocked in every possible configuration across all rows.

Level: Medium7 of 10
Topics: Intervals, Greedy, Prefix sum, Implementation
Solved: No attempts yet

Problem

Mr. Panda knows cats love laser toys, and decides to buy a laser toy for Rar the Cat. The laser toy that Mr. Panda bought consists of L evenly spaced lasers at the top of the toy, pointing downward. The 1st laser is located 0.5 units away from the leftmost edge and the Lth laser is located 0.5 units away from the rightmost edge of the toy. Every pair of adjacent lasers is 1 unit apart.

There are R rows of sliding walls, with each row containing a set of non-overlapping walls. Precisely, each row contains some number of walls whose total length is at most L. These walls can be slid to any position on the same row, as long as their relative positions along the row remain the same and they do not overlap. A wall of width x units (where x is a positive integer) will block exactly x consecutive lasers.

A possible toy with L = 11 and R = 3 is depicted in the diagram below:

Rar the Cat, being the curious cat as he is, wishes to know: Out of the L lasers in his toy, how many lasers will always be blocked by at least one wall in all possible configurations of the toy?

Input

Your program must read from standard input.

The first line of the input will contain two integers, L and R.

The next R lines of input will describe one row each. It will start with a single integer X, the number of sliding walls in the row. X integers will follow, indicating the widths of the X walls in that row, with the first integer indicating the width of the leftmost wall. Note that the sum of widths of the walls on each row cannot exceed L units.

Output

Your program should print to standard output.

Output a single integer on a single line, the number of lasers that will be blocked by at least one wall in all possible configurations of the toy.

Constraints

1 ≤ R ≤ 5 × 105
1 ≤ L ≤ 109
1 ≤ ΣX ≤ 5 × 105
1 ≤ Σwidth ≤ L for each row

Examples3

Example 1
Input
```
11 3
2 2 3
1 7
2 4 1
```
Expected output
```
3
```
Example 2
Input
```
10 3
3 1 5 1
4 2 2 3 1
3 1 6 2
```
Expected output
```
6
```
Example 3
Input
```
10 1
1 4
```
Expected output
```
0
```