레이팅 미적용JOI くんはお絵かきソフトで遊んでいる.
お絵かきソフトでは,縦 H 行,横 W 列の長方形のマス目に絵を描くことができる.それぞれのマスには色が定められており,色は 1 以上 10 9 以下の整数で表される.
上から 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 9 ) を指定すると,マス (x,y) の領域に含まれるマスの色がすべて c に変化する.
JOI くんはあるマス (x,y) と色 c を選び,そのマスと色を指定して塗りつぶしをちょうど 1 回使う.塗りつぶしを使った後のマス (x,y) の領域に含まれるマスの個数が JOI くんの得点となる.
JOI くんの得点として達成可能な最大値を求めるプログラムを作成せよ.
1 ≦ H ≦ 500 .
1 ≦ W ≦ 500 .
1 ≦ A i,j ≦ 10 9 ( 1 ≦ i ≦ H , 1 ≦ j ≦ W ).
入力される値はすべて整数である.
( 9 点) H = 1 .
( 32 点) H ≦ 30 , W ≦ 30 , A i,j ≦ 5 ( 1 ≦ i ≦ H , 1 ≦ j ≦ W ).
( 18 点) H ≦ 30 , W ≦ 30 .
( 10 点) A i,j ≦ 2 ( 1 ≦ i ≦ H , 1 ≦ j ≦ W ).
( 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 行に出力せよ.
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