색칠하기

문제

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)$ 와 색이 다른 칸에 들어가지 않고 이동할 수 있는 칸들의 모임을 여기서는 칸 $(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$ 를 골라, 그 칸과 색을 지정하여 색칠하기를 정확히 $1$ 번 사용한다. 색칠하기를 사용한 후 칸 $(x,y)$ 의 영역에 포함된 칸의 개수가 JOI 군의 점수가 된다.

JOI 군의 점수로 달성 가능한 최댓값을 구하는 프로그램을 작성하시오.

제한

• $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$ 점) 추가 제약이 없다.

입력

입력은 다음과 같은 형식으로 주어진다.
$H$ $W$
$A_{1,1}$ $A_{1,2}$ $\dots$ $A_{1,W}$
$A_{2,1}$ $A_{2,2}$ $\dots$ $A_{2,W}$
$:$
$A_{H,1}$ $A_{H,2}$ $\dots$ $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$ 의 제약을 만족한다.