Условие задачи
Сад JOI имеет форму квадрата, разделённого сеткой на $N$ строк по вертикали и $N$ столбцов по горизонтали. Клетка в $i$-й строке сверху ($1 \le i \le N$) и $j$-м столбце слева ($1 \le j \le N$) называется участком $(i, j)$.
Поскольку почва в саду JOI не слишком плодородна, на каждом участке можно посадить не более $1$ цветка $1$ определённого цвета. А именно, на участке $(i, j)$ можно посадить не более $1$ красного цветка, если $A_{i, j} =$ R, жёлтого, если $A_{i, j} =$ Y, и синего, если $A_{i, j} =$ B.
Директор K, управляющий этим садом, хочет посадить цветы по следующей процедуре, чтобы сад красиво смотрелся на аэрофотоснимке:
- Выбрать целое число $r$, обозначающее размер. При этом должно выполняться условие $0 \le r \le (N-1) \div 2$.
- Выбрать участок $(x, y)$, обозначающий центр. При этом должны выполняться условия $r+1 \le x \le N-r$ и $r+1 \le y \le N-r$.
- Выбрать цвета $c_0, c_1, c_2, \dots, c_r$, каждый из красного, жёлтого и синего.
- Для каждого участка $(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$ — целое число.
Подзадачи
- ($4$ балла) $N = 3$.
- ($13$ баллов) $N \le 50$.
- ($17$ баллов) $N \le 800$.
- ($14$ баллов) Существует не более $5$ пар $(i, j)$ ($1 \le i \le N, 1 \le j \le N$), для которых $A_{i, j} \neq$
R. - ($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}$ есть не менее $3$ символов
R. - ($36$ баллов) Дополнительных ограничений нет.
Входные данные
Входные данные подаются в следующем формате:
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}Выходные данные
Выведите в $1$ строке максимальное количество цветов, которое может посадить директор K.
Пример 1
Входные данные
3 RYR YBY BYY
Выходные данные
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
Выходные данные
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
Выходные данные
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
Выходные данные
85
Этот пример удовлетворяет ограничениям подзадач $2, 3, 4, 5, 6$.
Пример 5
Входные данные
10 RRRRRRRRRR RYRRRRRRRR RRRRYRRRRR RBRRRRRRRR RRRRRRRRYR RBRRRRRRRR RRRRBRRRRR RBRRRRRRRR RRRRRRRRYR RRRRRRRRRR
Выходные данные
25
Этот пример удовлетворяет ограничениям подзадач $2, 3, 5, 6$.