5. Цветные шарики 2d
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Имеется прямоугольное поле из $$$n \times m$$$ цветных шариков трёх возможных цветов. За один шаг можно поменять местами два любых шарика. Определите, за какое наименьшее число шагов можно сделать так, чтобы поле разбилось на одноцветные прямоугольники — по одному прямоугольнику каждого цвета (из имеющихся).

Входные данные

В первой строке входных данных записаны два целых числа $$$n$$$ и $$$m$$$. В следующих $$$n$$$ строках записаны по $$$m$$$ чисел 1, 2 или 3 — цвета шариков.

Выходные данные

Выведите единственное целое число — минимальное количество шагов. Если решения не существует, то выведите -1.

Система оценки

Подзадача 1 (до 20 баллов): $$$1 \le n, m \le 10$$$, цвета шариков могут быть только 1 или 2

Подзадача 2 (до 20 баллов): $$$1 \le n, m \le 1000$$$, цвета шариков могут быть только 1 и 2

Подзадача 3 (до 24 баллов): $$$1 \le n, m \le 10$$$, цвета шариков могут быть 1, 2 или 3

Подзадача 4 (до 36 баллов): $$$1 \le n, m \le 1000$$$, цвета шариков могут быть 1, 2 или 3

Примеры
Входные данные
3 4
1 2 1 1
2 1 1 3
3 3 3 1
Выходные данные
2
Входные данные
2 2
1 1
1 1
Выходные данные
0
Входные данные
2 3
1 1 1
1 1 2
Выходные данные
-1
Примечание

В первом примере достаточно заменить первые два шарика в первой строке и последние два шарика в последнем столбце.

Напоминание для пишущих на Python. Ввести набор целых чисел, записанных через пробел, можно так: 

c = [int(x) for x in input().split()]