Library shelf tidying

Time limit1sMemory limit64 MB

Summary

Given current and target shelf layouts, find the minimum number of books to lift when sliding a book into an empty spot on the same shelf costs nothing.

Level: Medium7 of 10
Topics: Dynamic programming, Binary search
Solved: No attempts yet

Problem

Librarian Jurica works in a library with $N$ shelves, and each shelf holds up to $M$ books. Jurica is taking inventory and wants to put every misplaced book back where it belongs. He moves a book in one of two ways.

He slides a book one place to the left or to the right on its own shelf. The place he slides it into has to be empty.
He lifts one book and puts it on an empty place of the same shelf or of any other shelf.

Jurica cannot slide a book while he holds one in his hands, and he never holds more than one book at a time.

Jurica's back has hurt ever since he carried the whole printed edition of Wikipedia from the first floor to the second, so he wants to put every book in place with as few lifts as he can. Find the smallest number of lifts he needs.

Input

The first line contains the integers $N$ and $M$ ( $1 \le N \le 1000$ , $1 \le M \le 1000$ ).

Each of the next $N$ lines contains $M$ integers, and the $i$ -th line describes the current state of the $i$ -th shelf. A 0 marks an empty place, and a number other than 0 means the book with that number sits in that place. If $K$ is the total number of books on the shelves, the books carry the distinct numbers 1 to $K$ .

The next $N$ lines describe the wanted state of the shelves in the same format. The same books appear in the initial state and in the wanted state.

Output

Print the smallest number of lifts on one line. Print -1 if the books cannot be arranged in the described way.

Hint

The first example goes like this. Jurica slides book 1 one place to the right. He lifts book 2 and puts it on the first place of the first shelf. He lifts book 5 and puts it on the fourth place of the second shelf.

Examples3

Example 1
Input
```
2 4
1 0 2 0
3 5 4 0
2 1 0 0
3 0 4 5
```
Expected output
```
2
```

Example 2

Input

Expected output

Example 3
Input
```
2 2
1 2
3 4
2 3
4 1
```
Expected output
```
-1
```