서가 정리

사서 유리차가 일하는 도서관에는 서가가 $N$ 개 있고, 서가 하나에는 책을 $M$ 권까지 꽂을 수 있다. 유리차는 장서를 점검하면서 제자리에 없는 책을 원래 자리로 되돌리려고 한다. 책을 옮기는 방법은 두 가지다.

• 같은 서가 안에서 책을 왼쪽이나 오른쪽으로 한 칸 민다. 미는 쪽 칸이 비어 있어야 한다.
• 책을 한 권 들어 올려 같은 서가나 다른 서가의 빈칸에 꽂는다.

유리차는 손에 책을 든 채로는 다른 책을 밀지 못하고, 한 번에 두 권 이상 들지도 못한다.

유리차는 인쇄판 위키백과 전집을 1층에서 2층으로 옮긴 뒤로 허리가 아프다. 그래서 책을 되도록 적게 들어 올려 모든 책을 제자리에 놓으려고 한다. 책을 들어 올리는 횟수의 최솟값을 구하여라.

첫 줄에 정수 $N$ 과 $M$ 이 주어진다 ($1 \le N \le 1000$, $1 \le M \le 1000$).

다음 $N$ 개 줄에는 각각 정수가 $M$ 개씩 주어지며, $i$ 번째 줄은 $i$ 번 서가의 현재 상태다. 0은 빈칸을 뜻하고, 0이 아닌 수는 그 번호의 책이 그 칸에 꽂혀 있다는 뜻이다. 서가에 꽂힌 책의 총 개수를 $K$ 라 하면 책 번호는 1부터 $K$ 까지 서로 다르다.

그 다음 $N$ 개 줄에는 같은 형식으로 원하는 최종 상태가 주어진다. 처음 상태와 최종 상태에 나오는 책은 서로 같다.

책을 들어 올리는 횟수의 최솟값을 한 줄에 출력한다. 위 방법으로 책을 정리할 수 없으면 -1을 출력한다.

첫 번째 예제는 이렇게 정리한다. 1번 책을 오른쪽으로 한 칸 민다. 2번 책을 들어 올려 첫 번째 서가의 첫 번째 칸에 꽂는다. 5번 책을 들어 올려 두 번째 서가의 네 번째 칸에 꽂는다.