CF838A.Binary Blocks

You are given an image, that can be represented with a 2-d n by m grid of pixels. Each pixel of the image is either on or off, denoted by the characters "0" or "1", respectively. You would like to compress this image. You want to choose an integer k > 1 and split the image into k by k blocks. If n and m are not divisible by k, the image is padded with only zeros on the right and bottom so that they are divisible by k. Each pixel in each individual block must have the same value. The given image may not be compressible in its current state. Find the minimum number of pixels you need to toggle (after padding) in order for the image to be compressible for some k. More specifically, the steps are to first choose k, then the image is padded with zeros, then, we can toggle the pixels so it is compressible for this k. The image must be compressible in that state.

你将获得一幅图像，该图像可用一个 $n \times m$ 的二维像素网格表示。图像中的每个像素要么开启（用字符 "1" 表示），要么关闭（用字符 "0" 表示）。你希望对该图像进行压缩。你需要选择一个整数 $k > 1$，并将图像划分为若干个 $k \times k$ 的块。若 $n$ 和 $m$ 不能被 $k$ 整除，则在图像的右侧和底侧仅用 0 进行填充，使得填充后的尺寸能被 $k$ 整除。每个 $k \times k$ 块内的所有像素值必须完全相同。当前给定的图像可能无法直接压缩。请找出：在填充之后，为使图像对某个 $k$ 可压缩，所需翻转（即 0 变 1 或 1 变 0）的最少像素数量。更具体地说，操作步骤如下：首先选定 $k$，然后对图像用 0 进行填充，最后可翻转若干像素，使得图像对该 $k$ 可压缩。最终状态下的图像必须满足可压缩性要求。

The first line of input will contain two integers n, m (2 ≤ n, m ≤ 2 500), the dimensions of the image.

The next n lines of input will contain a binary string with exactly m characters, representing the image.

输入的第一行包含两个整数 $n$ 和 $m$（$2 \leq n, m \leq 2\,500$），表示图像的尺寸。

接下来的 $n$ 行，每行包含一个长度恰好为 $m$ 的二进制字符串，表示该图像。

Print a single integer, the minimum number of pixels needed to toggle to make the image compressible.

输出一个整数，即为使图像可压缩所需切换的最少像素数量。

We first choose k = 2.

The image is padded as follows:

001000
101100
110010
000000

We can toggle the image to look as follows:

001100
001100
000000
000000

We can see that this image is compressible for k = 2.

我们首先选择 $k = 2$。

图像按如下方式补零（padding）：

001000  
101100  
110010  
000000  

我们可以对该图像进行翻转（toggle），使其变为如下形式：

001100  
001100  
000000  
000000  

可以看出，该图像对 $k = 2$ 是可压缩的。