Problem G: 【2023】积木

Memory Limit:128 MB Time Limit:1.000 S
Judge Style:Text Compare Creator:
Submit:19 Solved:6

Description

        小 X 在地上玩积木,每块积木都是一个 1*1*1 的正方体。地面可以看成一个 n*m 的网格,其中每一小格内都整齐地从下到上堆着若干块积木。其中第 i 行第 j 列中有 h[i][j]块积木。
        现在小 X 想要拿走一些积木,使得剩下来到积木组成一个正方体,正方体指的是长宽高都相同的长方体。
        小 X 想问你他最少拿掉多少块积木才能使得最后剩下来的积木组成一个正方体。

Input

第一行,2 个整数 n 和 m 表示地面的大小。
接下来 n 行,每行 m 个非负整数。第 i 行第 j 个数表示 h[i][j]。

Output

一行一个整数表示答案。

Sample Input Copy

3 3
2 2 1
3 2 2
3 1 2

Sample Output Copy

10

HINT

样例解释 1
拿完之后每个位置的积木数为:
2 2 0
2 2 0
0 0 0 一共拿掉(2-2)+(2-2)+(1-0)+(3-2)+(2-2)+(2-0)+(3-0)+(1-0)+(2-0)=1+1+2+3+1+2=10 块积木。

样例输入 2
5 5
4 4 3 4 3
3 4 3 3 3
3 3 1 4 4
3 4 4 3 3
4 3 4 4 4
样例输出 2
77

数据范围
本题共有 12 个测试点,每个测试点 10 分。
对于所有测试点 1<=n,m<=1000,0<=h[i][j]<=1000
对于测试点 1-3 :1<=n,m<=50
对于测试点 4-6 :1<=n,m<=200
对于测试点 7-9 :1<=n,m<=1000,0<=h[i][j]<=20

Source/Category