시간 제한 메모리 제한 제출 횟수 정답 횟수 (비율) 정답자 수
1.0 초 512 MB 1 1 (100%) 1
문제
도서관의 사서인 쥬리카는 그의 도서관에 $N$개의 선반을 가지고 있으며 각 선반에는 $M$권의 책이 놓일 수 있다. 쥬리카는 좋은 사서이므로 도서관의 리스트를 만들어 제자리에 놓여있지 않은 책을 제자리에 두려고 한다. 그는 책을 옮길 때 다음과 같이 옮긴다: - 책을 현재 놓여 있는 선반에서 한 칸 왼쪽이나 오른쪽으로 민다(해당하는 칸이 비어있을 경우). - 책을 선반에서 꺼내서 다른 선반의(혹은 같은 선반의) 비어있는 자리로 옮긴다. 쥬리카는 책을 들고 있으면서 다른 책을 옮기지 못한다. 다시 말하면 그는 한번에 한권의 책만 옮길 수 있다. 쥬리카는 위키피디아 특별 에디션을 들고 1층과 2층을 반복하여 날랐다가 허리에 요통이 왔다. 그래서 그는 최소한으로 책을 옮기려 한다. 그가 필요한 최소의 책을 옮기는 횟수는 얼마인가? (옆으로 미는 횟수는 세지 않는다.)
입력
첫 번째 줄에는 두 정수 $N$과 $M$이 주어진다$(1 \le N \le 1,000, 1 \le M \le 1,000)$. 그 다음에 오는 $N$개의 줄에는 $M$개의 정수가 주어지며 $i$번째 줄은 $i$번째 선반의 상태를 나타낸다. $0$은 그 자리가 비어 있음을 의미하며, 그 밖의 숫자는 그 자리에 놓여 있는 책의 번호를 의미한다. 모든 책은 $1$부터 $K$까지의 정수로 표현이 되며 $K$는 전체 책의 개수이다. 그 뒤에 다시 $N$개의 줄이 입력되며 각 줄에는 $M$개의 정수가 있고, $i$번째 줄은 $i$번째 선반이 최종적으로 되야 할 상태이다. 선반의 시작 상태와 최종 상태에서 등장하는 책들은 모두 같다.
출력
입력의 첫 번째 줄에는 최종 상태로 만들기 위한 최소의 옮기는 횟수를 출력하며, 만약 방법이 없을 경우엔 $-1$을 출력한다.
힌트
#### 채점 정보 전체 점수의 50%에 해당하는 데이터에서는 각 책은 시작 상태와 최종 상태에서 같은 선반에 놓여있다. ##### 입력 예제 1 ``` 2 4 1 0 2 0 3 5 4 0 2 1 0 0 3 0 4 5 ``` ##### 출력 예제 1 ``` 2 ``` ##### 입력 예제 2 ``` 3 3 1 2 3 4 5 6 7 8 0 4 2 3 6 5 1 0 7 8 ``` ##### 출력 예제 2 ``` 4 ``` ##### 입력 예제 3 ``` 2 2 1 2 3 4 2 3 4 1 ``` ##### 출력 예제 3 ``` -1 ```