题目描述

如果一个二进制矩阵的每一个偶数边长的正方形子矩阵中 $1$ 的个数都是奇数，则称该矩阵是“好”的。

给定一个由 $n$ 行 $m$ 列组成的二进制矩阵 $a$，请你求出最少需要修改多少个单元格，才能使其变为“好”的矩阵。如果无法做到，请输出 $-1$。

上述所有术语的正式定义请参考提示部分。

输入格式

输入的第一行包含两个整数 $n$ 和 $m$（$1 \leq n \leq m \leq 10^6$ 且 $n\cdot m \leq 10^6$），分别表示矩阵 $a$ 的行数和列数。

接下来的 $n$ 行，每行包含 $m$ 个字符，每个字符为 $0$ 或 $1$。如果第 $i$ 行第 $j$ 个字符为 $1$，则 $a_{i,j}=1$；如果为 $0$，则 $a_{i,j}=0$。

输出格式

输出最少需要修改多少个单元格，才能使 $a$ 变为“好”的矩阵。如果无法做到，输出 $-1$。

说明/提示

在第一个样例中，将 $a_{1,1}$ 改为 $0$，$a_{2,2}$ 改为 $1$ 即可满足条件。

你可以验证第二个样例无法通过任何方式使矩阵变为“好”的。

一些定义说明：

• 二进制矩阵指的是每个元素都是 $0$ 或 $1$ 的矩阵。
• 子矩阵由 $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$。
• 该子矩阵包含所有满足 $r_1 \leq i \leq r_2$ 且 $c_1 \leq j \leq c_2$ 的元素 $a_{i,j}$。
• 如果 $r_2-r_1 = c_2-c_1$ 且 $r_2-r_1+1$ 能被 $2$ 整除，则该子矩阵称为偶数边长的正方形子矩阵。

由 ChatGPT 4.1 翻译

样例

3 3
101
001
110

2

7 15
000100001010010
100111010110001
101101111100100
010000111111010
111010010100001
000011001111101
111111011010011

-1