配点: 100 点
問題文
JOI君正在玩画图软件。
在绘图软件中,垂直 H 行,横 W 您可以在列中的矩形网格上绘图。每个方格都有指定的颜色,颜色为 1 以上 10^9 由以下整数表示。
从上面 i 行目 (1 \leqq i \leqq H),从左起 j 列目 (1 \leqq j \leqq W) 它被称为 (i,j) 。目前,大众 (i,j) 的颜色是 A_{i,j} 。
质量 重复从 (i,j) 到与边缘接触的方块的移动,并且 (i,j) 是方块的集合,无需进入不同颜色的方块即可移动。质量 重复从 (i,j) 的面积 它被称为。
绘图软件包括填充 有一个名为的函数。该功能可以让您 (x,y) (1 \leqq x \leqq H,1 \leqq y \leqq W)和颜色 c (1 \leqq c \leqq 10^9) 指定质量 (x,y) 区域中包含的所有方块的颜色都是 更改为 c 。
JOI君是某个方块 (x,y) 和颜色 选择 c ,指定正方形和颜色,然后准确填充。 使用 1 次。使用填充后的正方形 区域 (x,y) 中包含的方格数就是JOI君的分数。
编写一个程序来找出 JOI-kun 可达到的最高分数。
制約
- 1 \leqq H \leqq 500.
- 1 \leqq W \leqq 500.
- 1 \leqq A_{i,j} \leqq 10^9 (1 \leqq i \leqq H,1 \leqq j \leqq W).
- 所有输入值都是整数。
小課題
- (9 点) H = 1.
- (32 点) H \leqq 30,W \leqq 30,A_{i,j} \leqq 5 (1 \leqq i \leqq H,1 \leqq j \leqq W).
- (18 点) H \leqq 30,W \leqq 30.
- (10 点) A_{i,j} \leqq 2 (1 \leqq i \leqq H,1 \leqq j \leqq W).
- (31 点)没有额外的限制。
入力
输入按照以下格式给出。
H W
A_{1,1} A_{1,2} \cdots A_{1,W}
A_{2,1} A_{2,2} \cdots A_{2,W}
\vdots
A_{H,1} A_{H,2} \cdots A_{H,W}
出力
JOI君可达到的最高分数。 在 1 行输出。
入力例 1
4 4 1 2 3 1 2 2 3 1 1 2 3 1 3 3 2 2
出力例 1
9
一开始,质量 (2,2) 区域中包含的单元格是 (1,2), (2,1), (2,2), (3,2) 的 4 。因此,质量 如果指定 (2,2) 和颜色 选择 3 并使用 fill,这些 4 方块的颜色 3 。

使用填充后,质量 将会有 (2,2) 区域中包含的单元格是 (1,2), (1,3), (2,1), (2,2), (2,3), (3,2), (3,3), (4,1), (4,2) 的 9 件。因此,JOI君的分数是 9 变为。
JOI君的分数 10 或更多是不可能的,所以9 。
此输入是一个小作业 2, 3, 5 满足约束。
入力例 2
2 10 1 2 2 1 3 3 3 3 1 1 1 1 1 1 1 1 1 3 3 3
出力例 2
18
此输入是一个小作业 2, 3, 5 满足约束。
入力例 3
5 5 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
出力例 3
25
此输入是一个小作业 2, 3, 4, 5 满足约束。