CF1391D.505

A binary matrix is called good if every even length square sub-matrix has an odd number of ones.

Given a binary matrix $a$ consisting of $n$ rows and $m$ columns, determine the minimum number of cells you need to change to make it good, or report that there is no way to make it good at all.

All the terms above have their usual meanings — refer to the Notes section for their formal definitions.

若一个二进制矩阵的每个偶数阶方子矩阵均包含奇数个 1，则称该矩阵为“好”矩阵。

给定一个由 $n$ 行 $m$ 列组成的二进制矩阵 $a$，请确定使其变为“好”矩阵所需的最少修改单元格数目；若无法使其变为“好”矩阵，则报告不存在可行方案。

上述所有术语均采用其通常含义——其形式化定义请参见“注释”部分。

The first line of input contains two integers $n$ and $m$ ($1 \leq n \leq m \leq 10^6$ and $n\cdot m \leq 10^6$) — the number of rows and columns in $a$, respectively.

The following $n$ lines each contain $m$ characters, each of which is one of 0 and 1. If the $j$-th character on the $i$-th line is 1, then $a_{i,j} = 1$. Similarly, if the $j$-th character on the $i$-th line is 0, then $a_{i,j} = 0$.

输入的第一行包含两个整数 $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$；若第 $i$ 行的第 $j$ 个字符为 0，则 $a_{i,j} = 0$。

Output the minimum number of cells you need to change to make $a$ good, or output $-1$ if it's not possible at all.

输出使 $a$ 变为“好”的数组所需修改的最少单元格数；如果根本无法实现，则输出 $-1$。

In the first case, changing $a_{1,1}$ to $0$ and $a_{2,2}$ to $1$ is enough.

You can verify that there is no way to make the matrix in the second case good.

Some definitions —

• A binary matrix is one in which every element is either $1$ or $0$.
• A sub-matrix is described by $4$ parameters — $r_1$, $r_2$, $c_1$, and $c_2$; here, $1 \leq r_1 \leq r_2 \leq n$ and $1 \leq c_1 \leq c_2 \leq m$.
• This sub-matrix contains all elements $a_{i,j}$ that satisfy both $r_1 \leq i \leq r_2$ and $c_1 \leq j \leq c_2$.
• A sub-matrix is, further, called an even length square if $r_2-r_1 = c_2-c_1$ and $r_2-r_1+1$ is divisible by $2$.

在第一种情况下，只需将 $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$。
• 该子矩阵包含所有满足 $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$ 整除，则称该子矩阵为偶数长度的正方形子矩阵。