Бинарная матрица называется хорошей, если каждая квадратная подматрица c четной длиной стороны содержит нечетное число единиц.
Для данной бинарной матрицы \(a\), состоящей из \(n\) строк и \(m\) столбцов, определите минимальное количество ячеек, которые нужно изменить, чтобы сделать ее хорошей, или сообщите, что ее вообще нельзя сделать хорошей.
Все вышеприведенные термины имеют свои обычные значения — обратитесь к разделу Примечания для их формальных определений.
Выходные данные
Выведите минимальное количество ячеек, которое нужно изменить, чтобы сделать \(a\) хорошей, или выведите \(-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\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3 3
101
001
110
|
2
|
|
2
|
7 15
000100001010010
100111010110001
101101111100100
010000111111010
111010010100001
000011001111101
111111011010011
|
-1
|