Problem Description

In Jurica's library, there are $n$ bookshelves, each with $m$ positions numbered from 1 to $m$ from left to right, and each position can hold a book. Jurica, being a diligent librarian, decides to conduct an inventory of the library and, if necessary, return books that are out of place to their original positions. Specifically, the book currently in position $j$ of shelf $i$ is labeled $a_{i,j}$ (if $a_{i,j}=0$, this position is empty), and the book originally in this position was labeled $b_{i,j}$ (if $b_{i,j}=0$, this position was originally empty). He can move books using the following operations:

• Operation 1: Move a book left or right within the shelf if there is an empty slot adjacent.
• Operation 2: Remove a book from a shelf and place it in an empty slot on the same or another shelf.

Jurica cannot move books if he is holding a book and he cannot hold more than one book at a time.

Due to a backache from moving the entire printed version of Wikipedia from the first floor to the second floor, Jurica wants to minimize the number of times he performs Operation 2. Please tell him the minimum number of times he needs to perform Operation 2, or inform him if it is impossible to return all books to their original positions.

Input Format

The input consists of $2n+1$ lines.

The first line contains two integers $n$ and $m$, representing the number of bookshelves and the number of positions on each shelf, respectively.
Lines 2 to $n+1$ contain $m$ integers each, describing the current arrangement of books on the shelves as $a_{i,j}$.
Lines $n+2$ to $2n+1$ contain $m$ integers each, describing the original arrangement of books on the shelves as $b_{i,j}$.

The input guarantees that the set of books in the original and current states is identical.

Output Format

If it is impossible for Jurica to return all books to their original positions, output a single integer $-1$.

Otherwise, output a single integer representing the minimum number of times Operation 2 needs to be performed.

Sample Input and Output

Sample Input #1

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

Sample Output #1

2

Sample Input #2

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

Sample Output #2

4

Sample Input #3

2 2
1 2
3 4
2 3
4 1

Sample Output #3

-1

Notes/Hints

[Sample 1 Explanation]

Here is the sequence of operations Jurica performs:

1. Operation 1: Move book 1 to its right position, making it the second book on its shelf.
2. Operation 2: Place book 2 in the first position on its shelf.
3. Operation 2: Place book 5 in the second position on its shelf.

It can be proven that there is no way to perform fewer than 2 instances of Operation 2.

[Data Range]

For 50% of the data, each book remains on the same shelf in both the initial and final states.
For all data, $1 \leqslant n, m \leqslant 1000$.

[Problem Source]

This problem is from COCI 2014-2015 CONTEST 7 T6 POLICE, configured with the original data, worth 160 points.

Provided by Eason_AC for translation and arrangement.

见题面 Input 部分

见题面 Output 部分