시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 512 MB 1 1 1 100.000%

문제

Mr. Panda knows cats love laser toys, and decides to invest in a laser toy for Rar the Cat. The laser toy that Mr. Panda has 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 adjacent lasers are of distance 1 unit.

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?

입력

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.

출력

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.

제한

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

예제 입력 1

11 3
2 2 3
1 7
2 4 1

예제 출력 1

3

The 5th, 6th and 7th lasers from the left will always be blocked by the wall of width 7 in row 2.

예제 입력 2

10 3
3 1 5 1
4 2 2 3 1
3 1 6 2

예제 출력 2

6

The 3rd, 4th, 5th, 6th, 7th and 9th lasers will always be blocked by at least one wall.

예제 입력 3

10 1
1 4

예제 출력 3

0

Every laser can pass through all rows in at least one configuration.