Binary Blocks

题意翻译

您会得到一张图像，该图像可用 $n \cdot m$ 的 2D 像素网格表示。图像的每个像素都处于打开或关闭状态，分别由字符 `0` 或 `1` 表示。您想压缩该图像。您想选择一个整数 $k > 1$ 并将图像分成 $k \cdot k$ 的块。如果 $n$ 或 $m$ 不能被 $k$ 整除，则在图像的右侧和底部填充 `0`，以便它们可以被 $k$ 整除。您可能需要切换一些像素的状态，使得每个块内所有像素状态一致——这样才是可压缩的。您可以任选 $k$，请您找到您需要切换状态的最小像素数。输出这个最小值。 更具体地说步骤是：您首先选择整数 $k > 1$，然后用 `0` 填充图像，然后切换一些像素的状态，使其对于您选择的 $k$ 可压缩。 Translated by [KHIN](/user/236807).

题目描述

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.

输入输出格式

输入格式

The first line of input will contain two integers $ n,m $ ( $ 2<=n,m<=2500 $ ), the dimensions of the image. The next $ n $ lines of input will contain a binary string with exactly $ m $ characters, representing the image.

输出格式

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

输入输出样例

输入样例 #1

3 5
00100
10110
11001

输出样例 #1

5

说明

We first choose $ k=2 $ . The image is padded as follows: `<br></br>001000<br></br>101100<br></br>110010<br></br>000000<br></br>`We can toggle the image to look as follows: `<br></br>001100<br></br>001100<br></br>000000<br></br>000000<br></br>`We can see that this image is compressible for $ k=2 $ .