题目内容

展厅里挂着一块高 $h$、宽 $w$ 的灯板。每盏灯标着一个整数编号。眼下亮着的样子记成表 $A$，希望呈现的样子记成表 $B$。

控制盒只有两种按钮，每种都能连按任意多次：

1. 上下对调：选两层紧挨着的灯，把这两整层交换（第 $p$ 层与第 $p+1$ 层，$1\le p<h$）。
2. 左右对调：选两列紧挨着的灯，把这两整列交换（第 $q$ 列与第 $q+1$ 列，$1\le q<w$）。

请问最少按多少次按钮，才能让 $A$ 与 $B$ 逐格相同。若怎样按都做不到，输出 $-1$。

同一块灯板上的编号允许相同。能对上的按法若不止一种，答案取次数最少的那种。

输入描述

第一行两个整数 $h$ 与 $w$，依次是层数和列数，满足 $2\le h\le 5$，$2\le w\le 5$。

接下来 $h$ 行，每行 $w$ 个整数，是当前灯号表 $A$（$1\le A_{p,q}\le 10^9$）。

再接下来 $h$ 行，每行 $w$ 个整数，是目标灯号表 $B$（$1\le B_{p,q}\le 10^9$）。

输出描述

若无法变成目标，输出 $-1$；否则输出最少按钮次数。

样例1

输入

2 2
5 6
7 8
7 8
5 6

输出

1

说明

把上下两层整层换一次，灯号就与目标逐格相同，所以答案是 $1$。只换左右列无法得到这个目标。

样例2

输入

2 3
8 1 4
9 2 6
1 4 8
2 6 9

输出

2

说明

两层的相对次序不用动。列要从 $(8,1,4)$ 变成 $(1,4,8)$，相当于原第 $2$ 列、第 $3$ 列、第 $1$ 列依次排到从左到右的位置。这个列次序有 $2$ 对逆序，相邻列交换 $2$ 次就能完成。例如先交换第 $1$、$2$ 列，再交换第 $2$、$3$ 列。

样例3

输入

2 2
2 5
7 9
2 7
5 9

输出

-1

说明

四种行列重排的结果分别是

• 不动：$\begin{smallmatrix}2&5\\7&9\end{smallmatrix}$
• 只换两列：$\begin{smallmatrix}5&2\\9&7\end{smallmatrix}$
• 只换两层：$\begin{smallmatrix}7&9\\2&5\end{smallmatrix}$
• 层和列都换：$\begin{smallmatrix}9&7\\5&2\end{smallmatrix}$

没有一种等于目标，因此输出 $-1$。