레이저

시간 제한1초메모리 제한512 MB

요약

각 행에 너비가 정해진 벽들이 미끄러질 수 있을 때, 모든 배치에서 항상 가려지는 레이저의 개수를 구한다.

난이도: 보통10점 중 7점
유형: 구간, 그리디, 누적 합, 구현
정답자: 아직 제출이 없습니다

문제

Mr. Panda는 고양이가 레이저 장난감을 좋아한다는 것을 알고, Rar the Cat을 위해 레이저 장난감을 사기로 했다. Mr. Panda가 산 레이저 장난감은 장난감 위쪽에 일정한 간격으로 놓인 L개의 레이저로 이루어져 있으며, 아래쪽을 향한다. 1번 레이저는 왼쪽 끝에서 0.5단위 떨어진 곳에 있고, L번 레이저는 오른쪽 끝에서 0.5단위 떨어진 곳에 있다. 인접한 레이저 사이의 거리는 1단위이다.

미끄러지는 벽이 R개의 행에 걸쳐 있고, 각 행에는 겹치지 않는 벽들이 들어 있다. 정확히 말해, 각 행에는 총 길이가 L 이하인 벽들이 몇 개 있다. 이 벽들은 행을 따라 상대적인 위치가 그대로 유지되고 겹치지 않는 한, 같은 행의 임의의 위치로 미끄러질 수 있다. 너비가 x단위인 벽(x는 양의 정수)은 정확히 연속한 x개의 레이저를 막는다.

L = 11, R = 3인 장난감의 예가 아래 그림에 나와 있다:

호기심 많은 고양이 Rar the Cat은 장난감의 모든 가능한 배치에서, L개의 레이저 중 몇 개가 항상 적어도 하나의 벽에 막히는지 알고 싶어 한다.

입력

프로그램은 표준 입력에서 읽는다.

입력의 첫 줄에는 두 정수 L과 R이 주어진다.

다음 R개의 줄은 각각 한 행을 나타낸다. 각 줄은 정수 X로 시작하며, X는 그 행에 있는 미끄러지는 벽의 개수이다. 이어서 X개의 정수가 주어지며, 이는 그 행에 있는 X개의 벽의 너비이고, 첫 번째 정수는 가장 왼쪽 벽의 너비이다. 각 행에서 벽 너비의 합은 L단위를 넘지 않는다.

출력

프로그램은 표준 출력에 출력한다.

장난감의 모든 가능한 배치에서 적어도 하나의 벽에 막히는 레이저의 개수를 한 줄에 하나의 정수로 출력한다.

제한

1 ≤ R ≤ 5 × 105
1 ≤ L ≤ 109
1 ≤ ΣX ≤ 5 × 105
각 행에서 1 ≤ Σwidth ≤ L

예제3

예제 1
입력
```
11 3
2 2 3
1 7
2 4 1
```
예상 출력
```
3
```
예제 2
입력
```
10 3
3 1 5 1
4 2 2 3 1
3 1 6 2
```
예상 출력
```
6
```
예제 3
입력
```
10 1
1 4
```
예상 출력
```
0
```