P13076 [NOISG 2019] Lasers

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

这个激光玩具的顶部有 $L$ 个间距均匀的激光，全部朝下。第 $1$ 个激光距离左边缘 $0.5$ 个单位，第 $L$ 个激光距离右边缘 $0.5$ 个单位，相邻激光之间距离为 $1$ 个单位。 该玩具共有 $R$ 排滑动的挡板，每排有若干不重叠的挡板。具体来说： - 每排有若干长度为正整数的挡板，总长度不超过 $L$。 - 同一排内，所有挡板可以整体平移，但挡板之间相对位置不变，且不会重叠。 - 一个宽度为 $x$ 的挡板可以完全阻挡连续 $x$ 个激光。 请你计算，在所有挡板可能的配置中，有多少个激光会始终被至少一个挡板阻挡。

第一行包含两个整数 $L$ 和 $R$。 接下来 $R$ 行描述每排的挡板情况，每行格式如下： - 一个整数 $X$，表示该排有 $X$ 个挡板。 - 接下来 $X$ 个整数，依次表示每个挡板的宽度，第一个整数是最左边挡板的宽度。 保证每排所有挡板的总宽度不超过 $L$。

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

【样例解释】 对于样例 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$ | 无额外限制 |