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 翻译