第22回日本情報オリンピック　二次予選

2022年12月13日
情報オリンピック日本委員会

問題文

JOI くんはお絵かきソフトで遊んでいる．

お絵かきソフトでは，縦 H 行，横 W 列の長方形のマス目に絵を描くことができる．それぞれのマスには色が定められており，色は 1 以上 10⁹ 以下の整数で表される．

上から i 行目 (1 ≦ i ≦ H)，左から j 列目 (1 ≦ j ≦ W) のマスをマス (i,j) と呼ぶ．現在，マス (i,j) の色は A_i,j である．

マス (i,j) から辺で接しているマスへの移動を繰り返し，マス (i,j) と色が異なるマスに入ることなく移動できるマスの集まりを，ここではマス (i,j) の領域と呼ぶ．

お絵かきソフトには，塗りつぶしという機能がある．この機能では，あるマス (x,y) (1 ≦ x ≦ H，1 ≦ y ≦ W) と色 c (1 ≦ c ≦ 10⁹) を指定すると，マス (x,y) の領域に含まれるマスの色がすべて c に変化する．

JOI くんはあるマス (x,y) と色 c を選び，そのマスと色を指定して塗りつぶしをちょうど 1 回使う．塗りつぶしを使った後のマス (x,y) の領域に含まれるマスの個数が JOI くんの得点となる．

JOI くんの得点として達成可能な最大値を求めるプログラムを作成せよ．

制約

• 1 ≦ H ≦ 500．
• 1 ≦ W ≦ 500．
• 1 ≦ A_i,j ≦ 10⁹ (1 ≦ i ≦ H，1 ≦ j ≦ W)．
• 入力される値はすべて整数である．

小課題

1. (9 点) H = 1．
2. (32 点) H ≦ 30，W ≦ 30，A_i,j ≦ 5 (1 ≦ i ≦ H，1 ≦ j ≦ W)．
3. (18 点) H ≦ 30，W ≦ 30．
4. (10 点) A_i,j ≦ 2 (1 ≦ i ≦ H，1 ≦ j ≦ W)．
5. (31 点) 追加の制約はない．

入力

入力は以下の形式で与えられる．
H W
A_1,1 A_1,2 … A_1,W
A_2,1 A_2,2 … A_2,W
:
A_H,1 A_H,2 … 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 を指定して塗りつぶしを使うと，下図のように，これらの 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 の制約を満たす．