D. 505
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Бинарная матрица называется хорошей, если каждая квадратная подматрица c четной длиной стороны содержит нечетное число единиц.

Для данной бинарной матрицы $$$a$$$, состоящей из $$$n$$$ строк и $$$m$$$ столбцов, определите минимальное количество ячеек, которые нужно изменить, чтобы сделать ее хорошей, или сообщите, что ее вообще нельзя сделать хорошей.

Все вышеприведенные термины имеют свои обычные значения  — обратитесь к разделу Примечания для их формальных определений.

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

Первая строка содержит два целых числа $$$n$$$ и $$$m$$$ ($$$1 \leq n \leq m \leq 10^6$$$ и $$$n\cdot m \leq 10^6$$$) — число строк и столбцов в $$$a$$$ соответственно.

Каждая из следующих $$$n$$$ строк содержит $$$m$$$ символов, каждый из которых равен 0 или 1. Если $$$j$$$-й символ в $$$i$$$-й строке равен 1, то $$$a_{i,j} = 1$$$. Аналогично, если $$$j$$$-й символ в $$$i$$$-й строке равен 0, то $$$a_{i,j} = 0$$$

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

Выведите минимальное количество ячеек, которое нужно изменить, чтобы сделать $$$a$$$ хорошей, или выведите $$$-1$$$, если это вообще невозможно.

Примеры
Входные данные
3 3
101
001
110
Выходные данные
2
Входные данные
7 15
000100001010010
100111010110001
101101111100100
010000111111010
111010010100001
000011001111101
111111011010011
Выходные данные
-1
Примечание

В первом случае достаточно заменить $$$a_{1,1}$$$ на $$$0$$$ и $$$a_{2,2}$$$ на $$$1$$$.

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

Некоторые определения  —

  • Бинарная матрица  — это матрица, в которой каждый элемент равен $$$1$$$ или $$$0$$$.
  • Подматрица описывается $$$4$$$ параметрами  — $$$r_1$$$, $$$r_2$$$, $$$c_1$$$ и $$$c_2$$$; здесь $$$1 \leq r_1 \leq r_2 \leq n$$$ и $$$1 \leq c_1 \leq c_2 \leq m$$$.
  • Эта подматрица содержит все элементы $$$a_{i,j}$$$, которые удовлетворяют как $$$r_1 \leq i \leq r_2$$$ так и $$$c_1 \leq j \leq c_2$$$.
  • Подматрица называется квадратом четной длины, если$$$r_2-r_1 = c_2-c_1$$$ и $$$r_2-r_1+1$$$ делится на $$$2$$$.