Problem11371--块(block)

11371: 块(block)

[Creator : ]
Time Limit : 1.000 sec  Memory Limit : 512 MiB

Description

Alice得到了一张由 $n\times m$ 个黑白像素点组成的图片,她想要压缩这张图片。压缩图片的过程如下:

1. 首先,选择一个正整数 $k\ (k>1)$,将图片划分成若干个 $k\times k$ 的小块。如果 $n,m$ 不能被 $k$ 整除,用白色像素点在图片的右边或下面补全,使补全成 $n,m$ 都能被 $k$ 整除。

2. 由于压缩时每个 $k\times k$ 的小块必须颜色一致(即全黑或者全白),所以需要先改变某些像素点的颜色,然后再进行压缩。

在Alice可以自由的选择任意一个大于 $1$ 的正整数 $k$ 作为小块的边长的情况下,请你告诉Alice,她至少需要改变多少个像素点的颜色。

Input

输入的第一行包含两个由空格隔开的正整数 $n,m\ (2\le n,m\le 1000)$,表示图片的尺寸。

接下来 $n$ 行,每行包含一个长度为 $m$ 的 01 串,表示Alice得到的那张图片。0 表示一个白色像素点,1 表示一个黑色像素点。

Output

输出一个整数,表示Alice要压缩她的图片至少需要改变颜色的像素点的个数。

Sample 1 Input

3 5
00100
10110
11001

Sample 1 Output

5

选择 $k=2$,图片被补全为,如下:

001000
101100
110010
000000
为使每个 $2\times 2$ 的小块颜色一致,改变颜色为,如下:

001100
001100
000000
000000
可以发现这是所有情况中改变颜色的像素点数最少的,改变了 $5$ 个像素点的颜色(答案为 $5$ 的改色方案不止这一种)。

Source/Category