Minimizing Operation 2 Moves in Library Book Arrangement

In Jurica’s library there are (n) shelves each with (m) positions (numbered from 1 to (m) from left to right). Every position can hold one book. Originally, the book at shelf (i) and position (j) was denoted by (b_{i,j}) (with (b_{i,j} = 0) meaning that the position was empty). Currently, shelf (i) and position (j) holds the book (a_{i,j}) (with (a_{i,j} = 0) meaning the position is empty).

Jurica wishes to restore every book to its original position using two types of operations:

1. Operation 1: A book can be moved horizontally (to an adjacent position on the same shelf) if that adjacent cell is empty.
2. Operation 2: A book can be picked up from a shelf and placed into any empty position on the same or a different shelf. Note that Jurica is not allowed to perform Operation 1 if he is holding a book and he cannot hold more than one book at any time.

Since Operation 1 doesn’t count toward his physical strain, Jurica wants to minimize the number of times he has to perform Operation 2. However, if the restoration is impossible (for example, if some book required in the original configuration is missing or extra books are present), you should output \(-1\).

There is a hidden trick: note that Operation 1 (sliding a book horizontally) does not change the relative order of books on a shelf. Therefore, for books that are already on their correct shelf according to \(b\), they can be rearranged by sliding only if their relative order is the same as in \(b\). Otherwise, some of these books must be removed (using Operation 2) and then reinserted in order.

More formally, let the target position of book \(x\) be \((t, p)\) (i.e. it should be on shelf \(t\) at position \(p\)). For each book present in the current configuration \(a\):

• If the book is on the wrong shelf (i.e. \(a_{i,j}\) with target shelf \(t \neq i\)), then it has to be moved using Operation 2.
• If the book is on the correct shelf (\(t = i\)), then the ones that can remain are those forming a longest increasing subsequence (LIS) of target positions. The remaining ones must be moved using Operation 2.

Thus, the minimum number of Operation 2 moves is equal to the sum for all shelves of the number of misplaced books plus the number of books on the correct shelf that are not in the longest increasing subsequence of target positions.

Your task is to compute and output the minimum number of Operation 2 moves required, or \(-1\) if restoration is impossible.

All formulas are given in \(\LaTeX\) notation.

inputFormat

The input begins with two integers (n) and (m) ( (1 \leq n, m \leq 1000) ) — the number of shelves and the number of positions per shelf.

Then follow (n) lines, each containing (m) integers. The (j)-th integer in the (i)-th line is (a_{i,j}) ((0 \leq a_{i,j} \leq 10^9)), representing the current configuration.

Then follow (n) lines, each containing (m) integers. The (j)-th integer in the (i)-th line is (b_{i,j}) ((0 \leq b_{i,j} \leq 10^9)), representing the original configuration.

It is guaranteed that for every nonzero book number in (b), it appears exactly once in (b). The current configuration (a) should have exactly the same set of nonzero books as (b>), though they may be misplaced.

outputFormat

Output a single integer: the minimum number of Operation 2 moves required to restore every book to its original position. If it is impossible to do so, output (-1).

sample

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

1