Description

打地鼠是这样的一个游戏: 地面上有一些地鼠洞, 地鼠们会不时从洞里探出头来很短时间后 又缩回洞中. 玩家的目标是在地鼠伸出头时, 用锤子砸其头部, 砸到的地鼠越多分数也就越高. 游戏中的锤子每次只能打一只地鼠, 如果多只地鼠同时探出头, 玩家只能通过多次 挥舞锤子的方式打掉所有的地鼠. 你认为这锤子太没用了, 所以你改装了锤子, 增加了锤子与地面的接触面积, 使其每次可以击打一片区域. 如果我们把地面看做 \(m \times n\) 的方阵, 其每个元素都代表一个地鼠洞, 那么锤子可以覆盖 \(R \times C\) 区域内的所有地鼠洞.

但是改装后的锤子有一个缺点: 每次挥舞锤子时, 对于这 \(R \times C\) 的区域中的所有地洞, 锤子会打掉恰好一只地鼠. 也就是说锤子覆盖的区域中, 每个地洞必须至少有 \(1\) 只地鼠, 且如果某个地洞中地鼠的个数大于 \(1\), 那么这个地洞只会有 \(1\) 只地鼠被打掉, 因此每次挥舞锤子时, 恰好有 \(R \times C\) 只地鼠被打掉.

由于锤子的内部结构过于精密, 因此在游戏过程中你不能旋转锤子 (即不能互换 \(R\) 和 \(C\)) . 你可以任意更改锤子的规格 (即你可以任意规定 \(R\) 和 \(C\) 的大小), 但是改装 锤子的工作只能在打地鼠前进行 (即你不可以打掉一部分地鼠后, 再改变锤子的规格). 你的任务是求出要想打掉所有的地鼠, 至少需要挥舞锤子的次数.

由于你可以把锤子的大小设置为 \(1 \times 1\), 因此本题总是有解的.

Input

第一行包含两个正整数 \(m, n\); 下面 \(m\) 行每行 \(n\) 个正整数描述地图, 每个数字表示 相应位置的地洞中地鼠的数量.

Output

输出一个整数, 表示最少的挥舞次数.

Sample Input

3 3
1 2 1
2 4 2
1 2 1

Sample Output

4

Data Range

对于 100% 的数据,\(1 \leq m, n \leq 100\), 其他数据不小于 \(0\), 不大于 \(10^5\).

Explanation

所有松鼠数量之和一定是某两个正整数的乘积的倍数, 这样就缩短了我们寻找的范围.

值得一提的是, 如果我们从较大的 \((R, C)\) 开始搜寻, 可能能够避免多次搜寻过多浪费 时间, 即时间可能退化到 \(O(n^2 m^2)\), 但是实际均摊接近 \(O(mn\sqrt{mn})\).

所以每一次枚举锤子的大小, 然后判断是否可以砸完所有地鼠就可以输出结果了.

Source Code


#include <iostream>
#include <cstdlib>
#include <cstdio>

#define rep(_var,_begin,_end) for(int _var=_begin;_var<=_end;_var++)
#define minimize(__x,__y) __x=min(__x,__y)
using namespace std;
typedef long long lli;
const int maxn = 110;

int n, m;
lli base[maxn][maxn], tmp[maxn][maxn];
lli sum;

bool judge(int x, int y)
{
    // Copying data to temporary storage
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            tmp[i][j] = base[i][j];
    // Checking result
    rep(i, 1, n) rep(j, 1, m) if (tmp[i][j]) {
        if (i+x-1 <= n && j+y-1 <= m) {
            // Within range, removing data
            lli orz = tmp[i][j];
            rep(k, 0, x-1) rep(l, 0, y-1) {
                tmp[i+k][j+l] -= orz;
                if (tmp[i+k][j+l] < 0)
                    return false;
            }
        } else {
            return false;
        }
    }
    return true;
}

int main(int argc, char** argv)
{
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++) {
            scanf("%lld", &base[i][j]);
            sum += base[i][j];
        }
    // Checking all possibilities.
    lli res = sum;
    for (int i = n; i >= 1; i--)
        for (int j = m; j >= 1; j--)
            if (sum % (i * j) == 0 && sum / (i * j) < res)
                if (judge(i, j))
                    minimize(res, sum / (i * j));
    // Output finale
    printf("%lld\n", res);
    return 0;
}