페이지가 로드되지 않나요? 여기를 눌러보면 고쳐질 수도 있어요.
Placeholder

#5838
서브태스크

그림그리기 (Painting) 2초 1024MB

문제

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 를 선택하고 그 매스와 색을 지정하고 채우기를 단 한 번 사용 합니다. 채우기를 사용한 후 매스 (x, y) 영역에 포함 된 매스 수는 JOI 군의 점수입니다.

JOI 군의 득점으로서 달성 가능한 최대치를 구하는 프로그램을 작성하라.


입력

입력은 다음 형식으로 제공됩니다.

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}

[제한]

1 ≦ H ≦ 500．

1≦W≦500．

1 ≦ A _{i,j} ≦ 10 ^9 (1 ≦ i ≦ H, 1 ≦ j ≦ W )．

입력 된 모든 값은 정수입니다.


출력

JOI 군의 득점으로서 달성 가능한 최대치를 1 행에 출력하라.


부분문제

번호 점수 조건
#19점

H = 1

#232점

H ≦ 30 , W ≦ 30 , A_{i,j} ≦ 5 (1 ≦ i ≦ H, 1 ≦ j ≦ W)

#318점

H ≦ 30，W ≦ 30

#410점

A_{i,j} ≦ 2 ( 1 ≦ i ≦ H , 1 ≦ j ≦ W )

#531점

추가 제한 없음


예제1

입력
44
1231
2231
1231
3322
출력
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

입력
210
1221333311
1111111333
출력
18

이 입력은 작은 이슈 2, 3, 5 의 제약을 만족시킨다


예제3

입력
55
11111
11111
11111
11111
11111
출력
25

이 입력은 작은 과제 2, 3, 4, 5 의 제약을 충족시킵니다


출처

JOI 2023 예선2

역링크