Задача №112800. Inventory
У библиотекаря Юрия есть шкаф, в котором N полок, и на каждой из полок могут стоять по M книг. Так как Юрий — хороший библиотекарь, то он решил сделать проверку своей библиотеки и, если это будет необходимо, переставить книги так, чтобы все книги стояли на своих местах. Переставлять книги он может следующими способами:
- передвинуть книгу на одно место влево или вправо по полке, если место слева или справа на той же полке свободно
- взять книгу с полки и поставить ее на свободное место на любую из полок
С тех пор, как Юрий перенес все тома печатного издания Википедии с первого на второй этаж, он испытывает сильные боли в спине, и поэтому он хочет переставить все книги на свои места так, чтобы при этом поднять книги как можно меньшее количество раз (при перемещении книги вправо или влево по полке первым из указанных способов Юрий книгу не поднимает). Какое наименьшее количество поднятий он должен совершить?
В первой строке находятся два числа: N и M ( 1 ≤ N ≤ 1000, 1 ≤ M ≤ 1000 ).
В каждой из последующих N строк находятся по M чисел, причем i - ая строка описывает текущее расположение книг на i - ой полке.
Число 0 означает свободное место на полке, а число, отличное от 0 , означает, что на этом месте стоит книга, имеющая номер равный этому числу. Все книги имеют различные номера от 1 до K , где K — общее количество книг на всех полках.
После этого следуют N строк, в каждой из которых по M чисел, причем i - ая строка описывает желаемое расположение книг на i - ой полке.
В текущем и в желаемом расположениях будут находиться книги с одними и теми же номерами и только они.
В первой и единственной строке должно содержаться минимальное количество поднятий, если из исходного расположения книг на полках возможно получить желаемое расположение, и - 1 , если желаемого расположения достичь указанными способами перестановки книг невозможно.
Подзадача 1. Для тестов этой подзадачи гарантируется, что для каждой книги полка, на которой она стоит в исходном расположении, и полка, на которой она должна стоять в желаемом расположении, будут совпадать. Решение этой подзадачи оценивается в 50 баллов.
Подзадача 2. Дополнительные ограничения отсутствуют. Решение оценивается в 50 баллов.
2 4 1 0 2 0 3 5 4 0 2 1 0 0 3 0 4 5
2