444. Таблички

Не решаласьСложная

Вам даны две таблички, в некоторых ячейках которых записаны положительные целые числа. От вас требуется превратить первую табличку во вторую за минимальное время, пользуясь двумя операциями:

  • Переместить число в соседнюю ячейку того же ряда, если эта ячейка не была занята. Такая операция занимает 0 секунд.
  • Переместить число в любую пустую ячейку в таблице. Такая операция занимает 1 секунду.

Формат ввода

В первой строке вводятся два числа n , m n, m ( 1 ≤ n , m ≤ 1000 1 \le n,m \le 1000 ) — высота и ширина табличек.

Далее вводится описание двух таблиц. Каждая таблица вводится как n n строк по m m чисел каждая. Число a i , j a_{i,j} ( 0 ≤ a i , j ≤ K 0 \le a_{i,j} \le K ) равно нулю, если соответствующая ячейка ( i , j ) (i, j) пустая, и равно от 1 до K K , если иначе. Все ненулевые элементы табличек различные, и K K равно количеству ненулевых элементов.

Гарантируется, что множество значений элементов в первой и второй табличках совпадает.

Формат вывода

Выведите одно число — минимальное время, нужное на перестановку элементов и превращение первой таблички во вторую. Если это невозможно, выведите -1.

Примечание

Одна из возможных последовательностей операций для первого теста:

  • Переместить число 1 в соседнюю ячейку справа за 0 секунд.
  • Переместить число 2 в первую ячейку первого ряда за 1 секунду.
  • Переместить число 5 в последнюю ячейку второго ряда за 1 секунду.

Ограничения

Ограничение времени
1 с
Ограничение памяти
256 МБ

Примеры

Пример 1

Ввод
2 4
1 0 2 0
3 5 4 0
2 1 0 0
3 0 4 5
Вывод
2

Пример 2

Ввод
3 3
1 2 3
4 5 6
7 8 0
4 2 3
6 5 1
0 7 8
Вывод
4

Пример 3

Ввод
2 2
1 2
3 4
2 3
4 1
Вывод
-1

Теги

18.1.8
Нужно войти, чтобы отправить решение.Войти