← 返回题目列表

AtCoder · utpc2021_i

I. 卡组

中文机器翻译题面 查看原题

配点 : 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