给您一个图像,可以用 2-d n x m 像素网格表示。图像的每个像素要么打开,要么关闭,分别用字符“0”或“1”表示。您想要压缩该图像。您想要选择一个整数 k > 1 并将图像分割为 k x k 块。如果 n 和 m 不能被 k 整除,则图像的右侧和底部仅填充零,以便它们可以被 k 整除。每个单独块中的每个像素必须具有相同的值。给定图像在当前状态下可能不可压缩。找到需要切换(填充后)的最小像素数,以便图像可压缩 k 个值。更具体地说,步骤是首先选择 k,然后用零填充图像,然后,我们可以切换像素,使其对于该 k 是可压缩的。图像在该状态下必须是可压缩的。
输入
输入的第一行将包含两个整数 n, m (2 ≤ n, m ≤ 2 500),即图像的尺寸。
接下来的 n 行输入将包含一个恰好包含 m 个字符的二进制字符串,代表图像。
输出
打印单个整数,即切换使图像可压缩所需的最小像素数。
示例
输入 #1
3 5 00100 10110 11001
输出 #1
5
注意
我们首先选择 k = 2。
图像填充如下:
我们可以将图像切换为如下所示:
我们可以看到该图像在 k = 2 时是可压缩的。