AT_utpc2021_i.Card Decks

有 $N$ 个牌堆，每个牌堆由 $M$ 张卡片组成，每张卡片上分别写有 $1$ 到 $M$ 的某个数字，每个数字在每个牌堆中只出现一次。对于第 $i$ 个牌堆，从上到下第 $j$ 张卡片上写着 $a_{i,j}$。

你可以对这些牌堆任意顺序、任意次数地进行以下两种操作：

• 操作 $1$：选择一个牌堆，将最上面的一张卡片移动到同一个牌堆的最底部。
• 操作 $2$：如果所有 $N$ 个牌堆最上面的卡片上的数字都相同，则可以把这些卡片全部取出并吃掉。

请问，为了吃掉所有卡片，最少需要进行多少次操作 $1$？

输入以如下格式从标准输入读入。

$N$ $M$
$a_{1,1}$ $a_{1,2}$ $\ldots$ $a_{1,M}$
$\vdots$
$a_{N,1}$ $a_{N,2}$ $\ldots$ $a_{N,M}$

请输出一个整数，表示最少需要进行多少次操作 $1$。

限制条件

• 输入均为整数。
• $1 \leq N \leq 2 \times 10^5$
• $1 \leq M \leq 22$
• $1 \leq a_{i,j} \leq M$
• $a_{i,j} \neq a_{i,k}$（$j \neq k$）

部分得分

• 若能正确解决 $1 \leq M \leq 16$ 的数据，将获得 $30$ 分。

样例说明 1

可以按如下方式进行操作：

• 对牌堆 $2$ 执行操作 $1$。
• 对牌堆 $4$ 执行操作 $1$。
• 执行操作 $2$（此时所有牌堆最上面的卡片都是 $2$）。
• 对牌堆 $1$ 执行操作 $1$。
• 对牌堆 $2$ 执行操作 $1$。
• 执行操作 $2$（此时所有牌堆最上面的卡片都是 $1$）。
• 执行操作 $2$（此时所有牌堆最上面的卡片都是 $3$）。

由 ChatGPT 4.1 翻译