题目背景

熊猫先生知道小猫非常喜欢激光玩具，于是他决定给 Rar the Cat 买一个激光玩具。

题目描述

这个激光玩具的顶部有 $L$ 个间距均匀的激光，全部朝下。第 $1$ 个激光距离左边缘 $0.5$ 个单位，第 $L$ 个激光距离右边缘 $0.5$ 个单位，相邻激光之间距离为 $1$ 个单位。

该玩具共有 $R$ 排滑动的挡板，每排有若干不重叠的挡板。具体来说：

• 每排有若干长度为正整数的挡板，总长度不超过 $L$。
• 同一排内，所有挡板可以整体平移，但挡板之间相对位置不变，且不会重叠。
• 一个宽度为 $x$ 的挡板可以完全阻挡连续 $x$ 个激光。

请你计算，在所有挡板可能的配置中，有多少个激光会始终被至少一个挡板阻挡。

输入格式

第一行包含两个整数 $L$ 和 $R$。

接下来 $R$ 行描述每排的挡板情况，每行格式如下：

• 一个整数 $X$，表示该排有 $X$ 个挡板。
• 接下来 $X$ 个整数，依次表示每个挡板的宽度，第一个整数是最左边挡板的宽度。

保证每排所有挡板的总宽度不超过 $L$。

输出格式

输出一个整数，表示始终被至少一个挡板阻挡的激光数量。

11 3
2 2 3
1 7
2 4 1

3

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

6

10 1
1 4

0

提示

【样例解释】

对于样例 1：

第 $2$ 排有一个宽度为 $7$ 的挡板，它无论怎么移动，第 $5$、$6$、$7$ 号激光总会被阻挡。

对于样例 2：

第 $3$、$4$、$5$、$6$、$7$、$9$ 号激光始终被至少一个挡板阻挡。

对于样例 3：

所有激光在至少一种挡板配置下都可以通过。

【数据范围】

• $1 \leq R \leq 5 \times 10^5$
• $1 \leq L \leq 10^9$
• $1 \leq \sum X \leq 5 \times 10^5$
• 每排所有挡板宽度和不超过 $L$

子任务编号	分值	额外限制
$1$	$10$	$R = 1,\ X = 1$
$2$	$14$	$X = 1$
$3$	$20$	$R = 2,\ 1 \leq L \leq 10^6$
$4$	$21$	$1 \leq L \leq 10^3,\ 1 \leq \sum X \leq 10^3$
$5$	$22$	$1 \leq L \leq 10^6$
$6$	$13$	无额外限制