P7796 [COCI 2014/2015 #7] POLICE

In librarian Jurica's library, there are $n$ bookshelves, and each bookshelf has $m$ positions, numbered from $1$ to $m$ from left to right. Each position can hold one book. Jurica is a good librarian, so he decides to take inventory of the library and, if necessary, return books that are not in their correct positions to where they originally belonged. Specifically, the book currently placed at position $j$ on bookshelf $i$ is numbered $a_{i,j}$ (if $a_{i,j}=0$, it means the position is currently empty), while the book that originally belonged to this position is numbered $b_{i,j}$ (if $b_{i,j}=0$, it means the position was originally empty). He moves books using the following operations: - Operation $1$: If there is an empty position to the left or right, a book can be moved left or right along the same bookshelf. - Operation $2$: Take a book off a bookshelf and place it into an empty position on the same bookshelf or on another bookshelf. Careful Jurica cannot move books while holding a book in his hands. Also, he **cannot hold more than one book at the same time**. Ever since he had to move all volumes of the printed edition of Wikipedia from the first floor to the second floor, Jurica has had back pain. Because his back hurts, he now wants to put all books into their correct places with as little carrying as possible. Please tell him the minimum number of times he needs to perform **operation $2$**, or tell him that it is impossible to restore all books to their original positions.

The input consists of $2n+1$ lines. The first line contains two integers $n,m$, representing the number of bookshelves and the number of positions on each bookshelf. Lines $2$ to $n+1$ each contain $m$ integers $a_{i,j}$, describing the current arrangement of books on the shelves. Lines $n+2$ to $2n+1$ each contain $m$ integers $b_{i,j}$, describing the original arrangement of books on the shelves. **The input guarantees that the sets of books appearing in the original and current states are exactly the same.**

If Jurica cannot restore all books to their original positions, output a single integer $-1$. Otherwise, output a single integer on one line, representing the minimum number of times **operation $2$** needs to be performed.

**[Sample 1 Explanation]** Below is Jurica's sequence of operations: 1. Operation $1$: Move book $1$ to the position on its right, i.e. the second position on its bookshelf. 2. Operation $2$: Carry book $2$ to the first position on its bookshelf. 3. Operation $2$: Carry book $5$ to the second position on its bookshelf. It can be proven that there is no solution with fewer executions of operation $2$. **[Constraints]** For $50\%$ of the testdata, each book is guaranteed to stay on the same bookshelf in both the initial and final states. For all testdata, $1\leqslant n,m\leqslant 1000$. **[Source]** This problem is from **_[COCI 2014-2015](https://hsin.hr/coci/archive/2014_2015/) [CONTEST 7](https://hsin.hr/coci/archive/2014_2015/contest7_tasks.pdf) T6 POLICE_**, using the original testdata settings, with a full score of $160$ points. Translated and整理 (pinyin: zhengli) by [Eason_AC](https://www.luogu.com.cn/user/112917). Translated by ChatGPT 5