题目描述

有 $N$ 组牌堆，每组牌堆由写有 $1$ 到 $M$ 之间整数的卡片组成。第 $i$ 个牌堆有 $K_i$ 张卡片，从上到下第 $j$ 张卡片上写的整数为 $A_{i,j}$。

卡片上的整数最初满足以下约束：

• 对于每个整数 $x\ (1\leq x\leq M)$，写有 $x$ 的卡片恰好出现在 $N$ 个牌堆中的两个不同牌堆中，每个牌堆各有一张。
• 每个牌堆最上面一张卡片上的整数互不相同。

对于这 $N$ 个牌堆，可以进行如下操作：

• 选择一个仍有卡片的牌堆，丢弃最上面的一张卡片。但丢弃后，所有仍有卡片的牌堆的最上面一张卡片上的整数必须互不相同。

请你求出最多可以进行多少次操作。

输入格式

输入以如下格式从标准输入给出。

$N$ $M$ $K_1$ $A_{1,1}$ $A_{1,2}$ $\dots$ $A_{1,K_1}$ $K_2$ $A_{2,1}$ $A_{2,2}$ $\dots$ $A_{2,K_2}$ $\vdots$ $K_N$ $A_{N,1}$ $A_{N,2}$ $\dots$ $A_{N,K_N}$

输出格式

请输出答案。

样例 1

输入

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

输出

1

样例 2

输入

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

输出

12

样例 3

输入

3 3
2 1 2
2 2 3
2 3 1

输出

0

样例 4

输入

12 40
4 35 39 11 21
7 31 29 16 15 30 32 34
4 21 27 38 40
11 17 28 26 23 33 22 3 36 8 1 20
1 30
4 40 38 24 6
8 8 36 9 10 5 7 20 4
10 5 10 9 3 22 33 23 26 28 17
4 15 16 29 31
11 19 13 12 18 25 2 39 35 7 14 37
3 4 1 14
13 24 27 11 2 25 18 12 13 19 32 37 6 34

输出

53

说明/提示

限制条件

• $2 \leq N \leq M$
• $2 \leq M \leq 2 \times 10^5$
• $1 \leq K_i \leq M$
• $1 \leq A_{i,j} \leq M$
• 对于每个整数 $x\ (1\leq x\leq M)$，$x=A_{i,j}$ 成立的 $i,j$ 组合恰好有 $2$ 个，且这两个 $i$ 互不相同。
• $A_{i,1}\ (1\leq i\leq N)$ 互不相同。
• 输入的所有值均为整数。

样例解释 1

一开始对第 $1$ 个牌堆进行操作后，该牌堆的卡片从上到下依次为 $2,3,4$。此时如果再次对第 $1$ 个牌堆操作，则第 $1$ 个和第 $2$ 个牌堆的最上面一张卡片上的整数都会变成 $3$，因此不能再对第 $1$ 个牌堆操作。同理也不能对第 $2$ 个牌堆操作。因此如果一开始对第 $1$ 个牌堆操作，最多只能操作 $1$ 次。如果一开始对第 $2$ 个牌堆操作，最多也只能操作 $1$ 次，所以答案是 $1$。

样例解释 2

通过合理操作可以丢弃所有卡片。

样例解释 3

有时一次操作都无法进行。

由 ChatGPT 4.1 翻译