정원 2

문제

JOI 정원은 세로 $N$ 행, 가로 $N$ 열의 격자 모양으로 나뉜 정사각형 모양을 하고 있다. 위에서 $i$ 번째 행 ($1 \le i \le N$), 왼쪽에서 $j$ 번째 열 ($1 \le j \le N$) 의 칸은 구역 $(i, j)$ 라고 부른다.

JOI 정원은 토양이 그다지 좋지 않기 때문에, 각 구역에는 특정한 $1$ 종류의 색의 꽃을 최대 $1$ 송이만 심을 수 있다. 구체적으로는, 구역 $(i, j)$ 에는 $A_{i, j} =$ R 일 때 빨강, $A_{i, j} =$ Y 일 때 노랑, $A_{i, j} =$ B 일 때 파랑 색의 꽃을 최대 $1$ 송이만 심을 수 있다.

여기서, 이 정원의 관리자인 K 이사장은 항공 사진을 찍었을 때의 보기 좋음을 위해, 다음 절차로 꽃을 심으려고 한다.

1. 크기를 나타내는 정수 $r$ 을 정한다. 단 $0 \le r \le (N-1) \div 2$ 를 만족해야 한다.
2. 중심을 나타내는 구역 $(x, y)$ 를 정한다. 단 $r+1 \le x \le N-r$, $r+1 \le y \le N-r$ 을 만족해야 한다.
3. 색 $c_{0}, c_{1}, c_{2}, \dots , c_{r}$ 을 각각 빨강 · 노랑 · 파랑 중에서 골라 정한다.
4. 각 구역 $(x', y')$ 에 대하여, $d = |x'-x| + |y'-y|$ 에 따라 다음 규칙으로 꽃을 심는다. 단, $|t|$ 는 $t$ 의 절댓값을 나타낸다. $d \le r$ 이면, 구역 $(x', y')$ 에는 색 $c_{d}$ 의 꽃을 심는다. $d > r$ 이면, 구역 $(x', y')$ 에는 꽃을 심지 않는다.

정원의 크기, 각 구역에 심을 수 있는 꽃의 색의 정보가 주어졌을 때, K 이사장이 심을 수 있는 꽃의 개수의 최댓값을 구하는 프로그램을 작성하시오.

제한

• $3 \le N \le 3\,500$.
• $A_{i, j}$ 는 R, Y, B 중 하나이다 ($1 \le i \le N, 1 \le j \le N$).
• $N$ 은 정수이다.

서브태스크

1. ($4$ 점) $N = 3$.
2. ($13$ 점) $N \le 50$.
3. ($17$ 점) $N \le 800$.
4. ($14$ 점) $A_{i, j} \neq$ R 을 만족하는 $(i, j)$ ($1 \le i \le N, 1 \le j \le N$) 는 $5$ 개 이하이다.
5. ($16$ 점) 어떤 $(i, j)$ ($1 \le i \le N-1, 1 \le j \le N-1$) 에 대해서도, $A_{i, j}$, $A_{i, j+1}$, $A_{i+1, j}$, $A_{i+1, j+1}$ 중에 R 이 $3$ 개 이상 존재한다.
6. ($36$ 점) 추가 제약이 없다.

입력

입력은 다음 형식으로 주어진다.
$N$
$A_{1,1}$ $A_{1,2}$ $\dots$ $A_{1,N}$
$A_{2,1}$ $A_{2,2}$ $\dots$ $A_{2,N}$
$︙$
$A_{N,1}$ $A_{N,2}$ $\dots$ $A_{N,N}$

출력

K 이사장이 심을 수 있는 꽃의 개수의 최댓값을 $1$ 줄로 출력한다.

예제 입력 1

3
RYR
YBY
BYY

예제 출력 1

5

$r = 1$, $(x, y) = (2, 2)$ 로 하고, $c_{0}$ 으로 파랑, $c_{1}$ 로 노랑을 고르면, 아래 그림과 같이 $5$ 송이의 꽃을 심을 수 있다. 단, 배경색은 각 구역에 심을 수 있는 꽃의 색을 나타낸다.

$6$ 송이 이상의 꽃을 심는 방법은 존재하지 않으므로, $5$ 를 출력한다.

이 예제는 서브태스크 $1, 2, 3, 6$ 의 제약을 만족한다.

예제 입력 2

9
YYRYBBBYR
BYYRRBYBB
RBRRBRBBY
RYRBRYRBR
YYBRYYYRB
RRYBRYRBR
RBYRBRBRB
BRYYRBBBR
RBBBYBRRY

예제 출력 2

25

$r = 3$, $(x, y) = (5, 6)$ 으로 하고, $c_{0}$ 으로 노랑, $c_{1}$ 로 노랑, $c_{2}$ 로 빨강, $c_{3}$ 으로 파랑을 고르면, 아래 그림과 같이 $25$ 송이의 꽃을 심을 수 있다. 단, 배경색은 각 구역에 심을 수 있는 꽃의 색을 나타낸다.

$26$ 송이 이상의 꽃을 심는 방법은 존재하지 않으므로, $25$ 를 출력한다.

이 예제는 서브태스크 $2, 3, 6$ 의 제약을 만족한다.

예제 입력 3

6
RBYRBY
BYRBYR
YRBYRB
RBYRBY
BYRBYR
YRBYRB

예제 출력 3

1

이 예제는 서브태스크 $2, 3, 6$ 의 제약을 만족한다.

예제 입력 4

20
RRRRRRRRRRRRRRRRRRRR
RRRRRRRRRRRRRRRRRRRR
RRRRBRRRRRRRRRRRRYRR
RRRRRRRRRRRRRRRRRRRR
RRRRRRRRRRRRRRRRRRRR
RRRRRRRRRRRRRRRRRRRR
RRRRRRRRRRRYRRRRRRRR
RRRRRRRRRRRRRRRRRRRR
RRRRRRRRRRRRRRRRRRRR
RRRRRRRRRRRRRRRRRRRR
RRRRRRRRRRRRRRRRRRRR
RRRRRYRRRRRRRRRRRRRR
RRRRRRRRRRRRRRRRRRRR
RRRRRRRRRRRRRRRRRRRR
RRRRRRRRRRRRRRRRRRBR
RRRRRRRRRRRRRRRRRRRR
RRRRRRRRRRRRRRRRRRRR
RRRRRRRRRRRRRRRRRRRR
RRRRRRRRRRRRRRRRRRRR
RRRRRRRRRRRRRRRRRRRR

예제 출력 4

85

이 예제는 서브태스크 $2, 3, 4, 5, 6$ 의 제약을 만족한다.

예제 입력 5

10
RRRRRRRRRR
RYRRRRRRRR
RRRRYRRRRR
RBRRRRRRRR
RRRRRRRRYR
RBRRRRRRRR
RRRRBRRRRR
RBRRRRRRRR
RRRRRRRRYR
RRRRRRRRRR

예제 출력 5

25

이 예제는 서브태스크 $2, 3, 5, 6$ 의 제약을 만족한다.