题目描述

在图书管理员 Jurica 的图书馆里有 $n$ 个书架，每个书架有 $m$ 个位置，从左往右编号为 $1$ 到 $m$，并且每个位置上都可以放一本书。Jurica 是一个好的图书管理员，所以他决定对图书馆进行清点，如果有必要，就把不在自己位置上的书放回原来的位置。具体来说，现在第 $i$ 个书架上的第 $j$ 个位置上面摆着编号为 $a_{i,j}$ 的书（如果 $a_{i,j}=0$ 说明这个位置上面现在没有书），而原来在这个位置上摆着编号为 $b_{i,j}$ 的书（如果 $b_{i,j}=0$ 说明这个位置上面原来没有书）。他以下列操作移动书籍：

• 操作 $1$：如果左边或右边有空位，可以在书架上向左或向右移动图书。
• 操作 $2$：从书架上取下一本书，放在该书架或其他书架的空位上。

细心的 Jurica 如果手中有书，就不能移动书。此外，他不能同时拿多于一本书。

自从他不得不把维基百科印刷版的所有书卷从一楼搬到二楼后，Jurica 就一直背痛。因为他的背很疼，所以现在他想把所有的书放好，尽量少搬。请告诉他需要的执行操作 $2$ 的次数最少是多少，或者告诉他根本不可能把这些书搬回原来的位置。

输入格式

输入共 $2n+1$ 行。

第一行输入两个整数 $n,m$，分别表示书架个数和每个书架上的位置个数。
第 $2$ 到 $n+1$ 行，每行输入 $m$ 个整数 $a_{i,j}$，描述现在书架上摆书的情况。
第 $n+2$ 到 $2n+1$ 行，每行输入 $m$ 个整数 $b_{i,j}$，描述原来书架上摆书的情况。

输入保证原来和现在出现的书籍完全相同。

输出格式

如果 Jurica 根本不可能把这些书搬回原来的位置，则仅输出一个整数 $-1$。

否则，输出一行一个整数，表示执行操作 $2$ 的最少次数。

2 4
1 0 2 0
3 5 4 0
2 1 0 0
3 0 4 5

2

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

4

2 2
1 2
3 4
2 3
4 1

-1

提示

【样例 1 解释】

以下是 Jurica 的操作序列：

1. 操作 $1$：把 $1$ 号书籍移动到它右边的位置，也就是它所在书架上的第二个位置。
2. 操作 $2$：把 $2$ 号书籍搬到它所在书架上的第一个位置。
3. 操作 $2$：把 $5$ 号书籍搬到它所在书架上的第二个位置。

可以证明没有更少执行操作 $2$ 的方案。

【数据范围】

对于 $50\%$ 的数据，保证每本书在初始和最终状态下都会在同一个书架上。
对于所有数据，$1\leqslant n,m\leqslant 1000$。

【题目来源】

本题来源自 COCI 2014-2015 CONTEST 7 T6 POLICE，按照原题数据配置，满分 $160$ 分。

由 Eason_AC 翻译整理提供。