给定一个大小为 $$$n \times m$$$ 的矩形矩阵,由从 $$$1$$$ 到 $$$2 \cdot 10^5$$$ 的整数组成。
只需一招,您就可以:
- 选择矩阵的任何元素并将其值更改为 $$$1$$$ 和 $$$n \cdot m$$$ 之间的任何整数(含);
- 取任意列并将其循环上移一个单元格(请参阅下面此类循环移位的示例)。
循环移位是一种操作,您可以选择一些 $$$j$$$ ($$$1 \le j \le m$$$) 并同时设置 $$$a_{1, j} := a_{2, j}, a_{2, j} := a_{3, j}, \dots, a_{n, j} := a_{1, j}$$$。
第一列循环移位示例
您想要执行最少的移动次数以使该矩阵看起来像这样:
换句话说,目标是获得矩阵,其中 $$$a_{1, 1} = 1, a_{1, 2} = 2, \dots, a_{1, m} = m, a_{2, 1} = m + 1, a_{2, 2} = m + 2, \dots, a_{n, m} = n \cdot m$$$ (即 $$$a_{i, j} = (i - 1) \cdot m + j$$$)执行的移动次数最少。
输入
输入的第一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$1 \le n, m \le 2 \cdot 10^5, n \cdot m \le 2 \cdot 10^5$$$) — 矩阵的大小。
接下来的 $$$n$$$ 行每行包含 $$$m$$$ 个整数。 $$$i$$$ 行和 $$$j$$$ 位置处的数字为 $$$a_{i, j}$$$ ($$$1 \le a_{i, j} \le 2 \cdot 10^5$$$)。
输出
打印一个整数 — 获得矩阵所需的最少移动次数,其中 $$$a_{1, 1} = 1, a_{1, 2} = 2, \dots, a_{1, m} = m, a_{2, 1} = m + 1, a_{2, 2} = m + 2, \dots, a_{n, m} = n \cdot m$$$ ($$$a_{i, j} = (i - 1)m + j$$$)。
示例
输入 #1
3 3 3 2 1 1 2 3 4 5 6
输出 #1
6
输入 #2
4 3 1 2 3 4 5 6 7 8 9 10 11 12
输出 #2
0
输入 #3
3 4 1 6 3 4 5 10 7 8 9 2 11 12
输出 #3
2
注意
在第一个示例中,您可以设置 $$$a_{1, 1} := 7, a_{1, 2} := 8$$$ 和 $$$a_{1, 3} := 9$$$,然后循环移动第一列、第二列和第三列,因此答案为 $$$6$$$。可以证明你无法得到更好的答案。
在第二个示例中,矩阵已经很好,因此答案是 $$$0$$$。
在第三个例子中,将第二列循环移位两次就足以获得一个好的矩阵,所以答案是$$$2$$$。