Problem Statement
JOI Garden has the shape of a square divided into a grid of $N$ rows vertically and $N$ columns horizontally. The cell in the $i$-th row from the top ($1 \le i \le N$) and the $j$-th column from the left ($1 \le j \le N$) is called section $(i, j)$.
Because JOI Garden is not blessed with very good soil, in each section, at most $1$ flower of $1$ specific color can be planted. Specifically, in section $(i, j)$, at most $1$ flower of color red when $A_{i, j} =$ R, yellow when $A_{i, j} =$ Y, and blue when $A_{i, j} =$ B can be planted.
Here, Director K, the manager of this garden, intends to plant flowers by the following procedure in order to make the garden look good when taking an aerial photograph:
- Decide an integer $r$ representing the size. Here, $0 \le r \le (N-1) \div 2$ must be satisfied.
- Decide a section $(x, y)$ representing the center. Here, $r+1 \le x \le N-r$ and $r+1 \le y \le N-r$ must be satisfied.
- Choose and decide colors $c_0, c_1, c_2, \dots, c_r$ each from red, yellow, and blue.
- For each section $(x', y')$, plant a flower according to $d = |x'-x| + |y'-y|$ by the following rules, where $|t|$ denotes the absolute value of $t$:
- If $d \le r$, plant a flower of color $c_d$ in section $(x', y')$.
- If $d > r$, do not plant a flower in section $(x', y')$.
Given the size of the garden and information on the colors of flowers that can be planted in each section, write a program to find the maximum number of flowers Director K can plant.
Constraints
- $3 \le N \le 3\,500$.
- $A_{i, j}$ is one of
R,Y,B($1 \le i \le N, 1 \le j \le N$). - $N$ is an integer.
Subtasks
- ($4$ points) $N = 3$.
- ($13$ points) $N \le 50$.
- ($17$ points) $N \le 800$.
- ($14$ points) There are at most $5$ pairs $(i, j)$ ($1 \le i \le N, 1 \le j \le N$) satisfying $A_{i, j} \neq$
R. - ($16$ points) For any $(i, j)$ ($1 \le i \le N-1, 1 \le j \le N-1$), there are at least $3$ occurrences of
Ramong $A_{i, j}$, $A_{i, j+1}$, $A_{i+1, j}$, $A_{i+1, j+1}$. - ($36$ points) No additional constraints.
Input
The input is given in the following format:
N
A_{1,1} A_{1,2} … A_{1,N}
A_{2,1} A_{2,2} … A_{2,N}
︙
A_{N,1} A_{N,2} … A_{N,N}Output
Print the maximum number of flowers Director K can plant in $1$ line.
Sample 1
Input
3 RYR YBY BYY
Output
5
If we set $r = 1$ and $(x, y) = (2, 2)$, and choose blue as $c_0$ and yellow as $c_1$, we can plant $5$ flowers as shown in the figure below. Here, the background color indicates the color of the flower that can be planted in each section.
Since there is no way to plant $6$ or more flowers, print $5$.
This sample input satisfies the constraints of Subtasks $1, 2, 3, 6$.
Sample 2
Input
9 YYRYBBBYR BYYRRBYBB RBRRBRBBY RYRBRYRBR YYBRYYYRB RRYBRYRBR RBYRBRBRB BRYYRBBBR RBBBYBRRY
Output
25
If we set $r = 3$ and $(x, y) = (5, 6)$, and choose yellow as $c_0$, yellow as $c_1$, red as $c_2$, and blue as $c_3$, we can plant $25$ flowers as shown in the figure below. Here, the background color indicates the color of the flower that can be planted in each section.
Since there is no way to plant $26$ or more flowers, print $25$.
This sample input satisfies the constraints of Subtasks $2, 3, 6$.
Sample 3
Input
6 RBYRBY BYRBYR YRBYRB RBYRBY BYRBYR YRBYRB
Output
1
This sample input satisfies the constraints of Subtasks $2, 3, 6$.
Sample 4
Input
20 RRRRRRRRRRRRRRRRRRRR RRRRRRRRRRRRRRRRRRRR RRRRBRRRRRRRRRRRRYRR RRRRRRRRRRRRRRRRRRRR RRRRRRRRRRRRRRRRRRRR RRRRRRRRRRRRRRRRRRRR RRRRRRRRRRRYRRRRRRRR RRRRRRRRRRRRRRRRRRRR RRRRRRRRRRRRRRRRRRRR RRRRRRRRRRRRRRRRRRRR RRRRRRRRRRRRRRRRRRRR RRRRRYRRRRRRRRRRRRRR RRRRRRRRRRRRRRRRRRRR RRRRRRRRRRRRRRRRRRRR RRRRRRRRRRRRRRRRRRBR RRRRRRRRRRRRRRRRRRRR RRRRRRRRRRRRRRRRRRRR RRRRRRRRRRRRRRRRRRRR RRRRRRRRRRRRRRRRRRRR RRRRRRRRRRRRRRRRRRRR
Output
85
This sample input satisfies the constraints of Subtasks $2, 3, 4, 5, 6$.
Sample 5
Input
10 RRRRRRRRRR RYRRRRRRRR RRRRYRRRRR RBRRRRRRRR RRRRRRRRYR RBRRRRRRRR RRRRBRRRRR RBRRRRRRRR RRRRRRRRYR RRRRRRRRRR
Output
25
This sample input satisfies the constraints of Subtasks $2, 3, 5, 6$.