配点 : 100 点
問題文
1 它们的编号最大为 M 的数字被一一写入。 由 M 卡牌组成的一副牌是 有 N 件。 i 从甲板顶部 j 在第二页上, 写入 a_{i, j} 。
您可以对这些牌组执行以下操作: 2 您可以按照任意顺序多次执行每种类型的操作。
- 操作 1:甲板 1 选择一张并将顶牌移至同一副牌的底部。
- 操作 2:N 如果牌堆最上面的牌上写的数字都相同,则将它们全部拿走并吃掉。
吃掉所有卡牌所需的操作 1 的最小数量是多少?
制約
- 所有输入均为整数
- 1 \le N \le 2 \times 10^5
- 1 \le M \le 22
- 1 \leq a_{i, j} \leq M
- a_{i, j} \neq a_{i, k} (j \neq k)
部分点
- 1 \le M \le 16 的数据集 30 分被给予。
入力
输入将以以下形式通过标准输入给出。
N M
a_{1, 1} \ldots a_{1, M}
\vdots
a_{N, 1} \ldots a_{N, M}
出力
答案 对于 1 行输出。
入力例 1
4 3 2 3 1 1 2 3 2 1 3 3 2 1
出力例 1
4
只需执行以下操作: 对
- 山札 2 进行操作 执行 1 。 执行
- 山札 4 进行操作 执行 1 。 执行
- 操作 2 。 (所有牌组的顶牌是 2 。 ) 对于
- 山札 1 进行操作 执行 1 。 执行
- 山札 2 进行操作 执行 1 。 执行
- 操作 2 。 (所有牌组的顶牌是 1 。 ) 对于
- 操作 2 。 (所有牌组的顶牌是 3 。 ) 对于
入力例 2
7 6 1 2 3 4 5 6 3 5 6 1 4 2 2 5 4 3 6 1 5 1 2 4 6 3 3 2 6 5 4 1 4 1 2 5 3 6 6 5 4 3 1 2
出力例 2
35