题目描述

给定两个均为$H$行$W$列的网格$A$和$B$。

对于满足$1 \leq i \leq H$且$1 \leq j \leq W$的每一对整数$(i, j)$，$(i, j)$表示网格中第$i$行第$j$列的单元格。网格$A$的单元格$(i, j)$中包含整数$A_{i, j}$，网格$B$的单元格$(i, j)$中包含整数$B_{i, j}$。

你可以重复执行以下操作任意次数（包括零次），每次操作需选择执行以下其中一种：

• 选择一个满足$1 \leq i \leq H-1$的整数$i$，交换网格$A$的第$i$行和第$(i+1)$行；
• 选择一个满足$1 \leq i \leq W-1$的整数$i$，交换网格$A$的第$i$列和第$(i+1)$列。

请判断是否可以通过重复执行上述操作，使网格$A$与网格$B$完全相同。若可以，输出所需的最少操作次数；若不可以，输出$-1$。

注：当且仅当对于所有满足$1 \leq i \leq H$且$1 \leq j \leq W$的整数对$(i, j)$，网格$A$的单元格$(i, j)$中的整数与网格$B$的单元格$(i, j)$中的整数相等时，网格$A$与网格$B$视为完全相同。

题目约束

• 所有输入值均为整数；
• $2 \leq H, W \leq 5$；
• $1 \leq A_{i, j}, B_{i, j} \leq 10^9$。

输入格式

输入数据从标准输入按以下格式给出：

$H$ $W$

$A_{1, 1}$ $A_{1, 2}$ $\cdots$ $A_{1, W}$

$A_{2, 1}$ $A_{2, 2}$ $\cdots$ $A_{2, W}$

$\vdots$

$A_{H, 1}$ $A_{H, 2}$ $\cdots$ $A_{H, W}$

$B_{1, 1}$ $B_{1, 2}$ $\cdots$ $B_{1, W}$

$B_{2, 1}$ $B_{2, 2}$ $\cdots$ $B_{2, W}$

$\vdots$

$B_{H, 1}$ $B_{H, 2}$ $\cdots$ $B_{H, W}$

输出格式

若无法通过操作使网格$A$与网格$B$相同，输出$-1$；否则输出将网格$A$变为网格$B$所需的最少操作次数。

样例输入1

4 5
1 2 3 4 5
6 7 8 9 10
11 12 13 14 15
16 17 18 19 20
1 3 2 5 4
11 13 12 15 14
6 8 7 10 9
16 18 17 20 19

样例输出1

3

样例解释1

对初始网格$A$执行以下操作可得到网格$B$：

1. 交换初始网格$A$的第4列和第5列，得到如下网格：

1 2 3 5 4
6 7 8 10 9
11 12 13 15 14
16 17 18 20 19

2. 交换上述网格的第2行和第3行，得到如下网格：

1 2 3 5 4
11 12 13 15 14
6 7 8 10 9
16 17 18 20 19

3. 交换上述网格的第2列和第3列，得到与网格$B$完全相同的网格：

1 3 2 5 4
11 13 12 15 14
6 8 7 10 9
16 18 17 20 19

以上操作共执行3次，且不存在更少次数的操作方式，因此输出3。

样例输入2

2 2
1 1
1 1
1 1
1 1000000000

样例输出2

-1

样例解释2

无论执行多少次操作，都无法使网格$A$与网格$B$匹配，因此输出$-1$。

样例输入3

3 3
8 1 6
3 5 7
4 9 2
8 1 6
3 5 7
4 9 2

样例输出3

0

样例解释3

初始状态下网格$A$已与网格$B$完全相同，无需执行任何操作，因此输出0。

样例输入4

5 5
710511029 136397527 763027379 644706927 447672230
979861204 57882493 442931589 951053644 152300688
43971370 126515475 962139996 541282303 834022578
312523039 506696497 664922712 414720753 304621362
325269832 191410838 286751784 732741849 806602693
806602693 732741849 286751784 191410838 325269832
304621362 414720753 664922712 506696497 312523039
834022578 541282303 962139996 126515475 43971370
152300688 951053644 442931589 57882493 979861204
447672230 644706927 763027379 136397527 710511029

样例输出4

20