시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 1024 MB141414100.000%

문제

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

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

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

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

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

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

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

입력

入力は以下の形式で与えられる.

H W
A1,1 A1,2  A1,W
A2,1 A2,2  A2,W
:
AH,1 AH,2  AH,W

출력

JOI くんの得点として達成可能な最大値を 1 行に出力せよ.

제한

  • 1 ≦ H ≦ 500
  • 1 ≦ W ≦ 500
  • 1 ≦ Ai,j ≦ 109 (1 ≦ i ≦ H1 ≦ j ≦ W).
  • 入力される値はすべて整数である.

서브태스크

번호배점제한
19

H = 1

232

H ≦ 30W ≦ 30Ai,j ≦ 5 (1 ≦ i ≦ H1 ≦ j ≦ W).

318

H ≦ 30W ≦ 30

410

Ai,j ≦ 2 (1 ≦ i ≦ H1 ≦ j ≦ W).

531

追加の制約はない.

예제 입력 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 の制約を満たす.

채점 및 기타 정보

  • 예제는 채점하지 않는다.