서가 정리

시간 제한1초메모리 제한64 MB

요약

현재 진열과 목표 진열이 주어질 때 같은 선반 안에서 빈칸으로 미는 이동은 무료로 두고 들어서 옮겨야 하는 책의 최소 개수를 구합니다.

난이도: 보통10점 중 7점
유형: 동적 계획법, 이분 탐색
정답자: 아직 제출이 없습니다

문제

사서 유리차가 일하는 도서관에는 서가가 $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번 책을 들어 올려 두 번째 서가의 네 번째 칸에 꽂는다.

예제3

예제 1
입력
```
2 4
1 0 2 0
3 5 4 0
2 1 0 0
3 0 4 5
```
예상 출력
```
2
```

예제 2

입력

예상 출력

예제 3
입력
```
2 2
1 2
3 4
2 3
4 1
```
예상 출력
```
-1
```