题目描述

有 $n$ 个展台按顺时针方向围成一圈。第 $i$ 个展台需要展示一座高为 $h_i$ 的积木塔，从下到上的颜色依次为

机器人始终使用同一个托盘搭塔。每次可以进行以下一种操作，代价均为 $1$：

• 移走塔顶的一块积木；
• 在塔顶放上一块指定颜色的积木。

机器人可以任选一个展台作为起点。开始时托盘为空，之后按顺时针方向访问所有展台各一次。

到达每个展台时，机器人需要通过增删塔顶积木，使托盘上的塔与该展台要求的塔完全相同。也就是说，机器人不会重新搭一座塔，而是把上一座塔逐步改成下一座塔。

例如，下图中先移走塔顶的红色积木，再放上一块黄色积木，就能把左边的塔变成右边的塔。

展台围成一圈，起点可以任意选择。例如选择 $3$ 号展台作为起点，则访问顺序为

完成最后一个展台的展示后，机器人可以直接停止，不需要清空托盘。

请计算完成所有展示最少需要多少次操作。

输入格式

从文件 tower.in 中读取数据。

第一行输入两个整数 $n,k$，分别表示展台数量和积木颜色的种数。颜色用 $1$ 到 $k$ 的整数编号。

接下来 $n$ 行，第 $i$ 行先输入一个整数 $h_i$，随后输入 $h_i$ 个整数 $c_{i,1},c_{i,2},\ldots,c_{i,h_i}$，按从下到上的顺序描述第 $i$ 个展台要求的塔。当 $h_i=0$ 时，这一行只包含整数 $0$。

输出格式

输出到文件 tower.out 中。

输出一个整数，表示最少操作次数。

4 4
3 1 2 3
2 1 2
2 1 4
3 1 4 3

7

3 2
0
2 1 2
1 1

3

样例解释

样例 #1 中，可以选择第 $1$ 个展台作为第一个展台。先用 $3$ 次操作搭出颜色依次为 $1,2,3$ 的塔；前往第 $2$ 个展台时移走塔顶积木；前往第 $3$ 个展台时先移走颜色为 $2$ 的积木，再放上颜色为 $4$ 的积木；最后放上一块颜色为 $3$ 的积木。总操作次数为 $3+1+2+1=7$。

样例 #2 中，可以选择要求空塔的第 $1$ 个展台作为第一个展台。随后用 $2$ 次操作搭出第 $2$ 个展台的塔，再移走塔顶积木即可完成第 $3$ 个展台的展示，共需 $3$ 次操作。

数据规模与约定

对于所有数据，保证：

• $1\le n\le 2\times 10^5$；
• $1\le k\le 10^9$；
• $0\le h_i\le 2\times 10^5\ (1\le i\le n)$；
• $1\le c_{i,j}\le k\ (1\le i\le n,\ 1\le j\le h_i)$；
• $\sum_{i=1}^{n}h_i\le 2\times 10^5$；
• 输入中的所有数均为整数。

本题采用子任务捆绑计分。只有通过某个子任务内的所有测试点，才能获得该子任务的分数。各子任务独立计分。

下发文件

下载三组测试数据，非真实测试数据