题目描述

JOI 君正在玩一个绘图软件。

在该绘图软件中，可以在一个 $H$ 行 $W$ 列的矩形网格上绘制图案。每个网格单元格都有一个颜色，颜色由 $1$ 到 $10^9$ 之间的整数表示。

从上往下第 $i$ 行（$1 \le i \le H$）、从左往右第 $j$ 列（$1 \le j \le W$）的单元格称为单元格 $(i,j)$。当前，单元格 $(i,j)$ 的颜色为 $A_{i,j}$。

从单元格 $(i,j)$ 出发，反复移动到与其相邻的、颜色相同的单元格，所能到达的所有单元格的集合，称为单元格 $(i,j)$ 的“区域”。

该绘图软件具有“填充”功能。使用该功能时，指定某个单元格 $(x,y)$（$1 \le x \le H$，$1 \le y \le W$）和颜色 $c$（$1 \le c \le 10^9$），则该单元格 $(x,y)$ 所在区域内的所有单元格颜色将全部变为 $c$。

JOI 君将选择某个单元格 $(x,y)$ 和颜色 $c$，并恰好使用一次“填充”功能。使用“填充”功能后，单元格 $(x,y)$ 所在区域内的单元格数量即为 JOI 君的得分。

请编写一个程序，求出 JOI 君可能获得的最大得分。

输入格式

输入数据按以下格式给出：

$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 君可能获得的最大得分。

4 4
1 2 3 1
2 2 3 1
1 2 3 1
3 3 2 2

9

2 10
1 2 2 1 3 3 3 3 1 1
1 1 1 1 1 1 1 3 3 3

18

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

25

提示

样例 1 解释

在初始状态下，单元格 $(2,2)$ 所在区域包含的单元格有 $(1,2)$、$(2,1)$、$(2,2)$、$(3,2)$，共 4 个。因此，若指定单元格 $(2,2)$ 和颜色 $3$ 并使用“填充”功能，这 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 的约束。

:::align{center} :::

数据范围

• $1 \le H \le 500$。
• $1 \le W \le 500$。
• $1 \le A_{i,j} \le 10^9$（$1 \le i \le H$，$1 \le j \le W$）。
• 所有输入值均为整数。

子任务

1. （9 分）$H = 1$。
2. （32 分）$H \le 30$，$W \le 30$，且 $A_{i,j} \le 5$（$1 \le i \le H$，$1 \le j \le W$）。
3. （18 分）$H \le 30$，$W \le 30$。
4. （10 分）$A_{i,j} \le 2$（$1 \le i \le H$，$1 \le j \le W$）。
5. （31 分）无额外约束。

翻译由 Qwen3-235B 完成。