Умова задачі
Сад 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$.