粉碎晶壁

意识迷宫的第五层，是一面由彩色晶体砌成的巨墙。晶体有红、蓝、绿、紫各种颜色，相同颜色的晶体互相粘连，形成大小不一的团块。每次可以引爆一个连通团块，团块越大，释放的能量就越强。但引爆后，上面的晶体会坠落填补空缺。

"这是Zero的色域防线。"Echo说，"你要把这面墙全部粉碎。得分是每次引爆团块大小的平方。目标是总分越高越好。"

"那就挑大的炸呗？"CC说。

"没这么简单。"你说，"炸掉一个大团块后，上面的晶体掉下来，可能会把原本分散的小团块拼成更大的，也可能把大团块拆碎。顺序很重要。"

"那咋个选？"

"要往前看。"你说，"每炸一个团块，都要想象炸完之后的局面。如果剩下的晶体怎么看都凑不出高分，那就说明当前这步可能走错了，应该换个团块试试。如果当前得分加上估计的上限都超不过已经找到的最好成绩，这条路就直接放弃。"

你把双手按在晶壁上，感知着每一个团块的脉动。你选了一个中等大小的紫色团块引爆——不是为了眼前的分数，而是为了让它上面的蓝色团块坠落后能和一个更大的蓝团块合并。屏幕上的分数跳动，最终停在了四千七百。

"又是四十七。"CC说。

"四千七百分。"Echo说，"那是Zero给这层防线设的阈值——超过它，就能撕开裂缝。"

"我们得了多少？"

"四千七。"Echo说，"刚好。"

题目描述

$n \times m$ 的方块矩阵，每次消除一个连通块，得分为块大小的平方。求消除所有方块的最高得分。

输入格式

$n, m$。然后矩阵。

输出格式

最高得分。

输入样例

3 3
...
.#.
...

输出样例

3 3
1 3
3 2
1 2

提示

• 逐块尝试消除顺序，预处理连通块。
• 优先消除大块。估算剩余局面上限以帮助决策。

木块消除后，墙壁裂开了一道缝隙。缝隙后面是第六层——也是最后一层。

"最后一道题。"Echo说。