Treść zadania

Ogród JOI ma kształt kwadratu podzielonego na siatkę $N$ wierszy w pionie i $N$ kolumn w poziomie. Pole w $i$-tym wierszu od góry ($1 \le i \le N$) i $j$-tej kolumnie od lewej ($1 \le j \le N$) nazywane jest sektorem $(i, j)$.

Ponieważ ogród JOI nie ma zbyt żyznej gleby, w każdym sektorze można zasadzić co najwyżej $1$ kwiat o $1$ określonym kolorze. Dokładniej, w sektorze $(i, j)$ można zasadzić co najwyżej $1$ kwiat koloru czerwonego, gdy $A_{i, j} =$ R, żółtego, gdy $A_{i, j} =$ Y, oraz niebieskiego, gdy $A_{i, j} =$ B.

Dyrektor K, zarządca tego ogrodu, zamierza zasadzić kwiaty według następującej procedury, aby ogród ładnie wyglądał na zdjęciu lotniczym:

1. Wybrać liczbę całkowitą $r$ oznaczającą rozmiar. Musi być spełniony warunek $0 \le r \le (N-1) \div 2$.
2. Wybrać sektor $(x, y)$ oznaczający środek. Muszą być spełnione warunki $r+1 \le x \le N-r$ oraz $r+1 \le y \le N-r$.
3. Wybrać i ustalić kolory $c_0, c_1, c_2, \dots, c_r$, każdy spośród czerwonego, żółtego i niebieskiego.
4. Dla każdego sektora $(x', y')$ zasadzić kwiat w zależności od $d = |x'-x| + |y'-y|$ według poniższych zasad, gdzie $|t|$ oznacza wartość bezwzględną liczby $t$:
   • Jeśli $d \le r$, w sektorze $(x', y')$ sadzimy kwiat o kolorze $c_d$.
   • Jeśli $d > r$, w sektorze $(x', y')$ nie sadzimy kwiatu.

Mając dany rozmiar ogrodu oraz informacje o kolorach kwiatów, które można zasadzić w poszczególnych sektorach, napisz program wyznaczający maksymalną liczbę kwiatów, jaką może zasadzić dyrektor K.

Ograniczenia

• $3 \le N \le 3\,500$.
• $A_{i, j}$ jest jednym ze znaków R, Y, B ($1 \le i \le N, 1 \le j \le N$).
• $N$ jest liczbą całkowitą.

Podzadania

1. ($4$ punkty) $N = 3$.
2. ($13$ punktów) $N \le 50$.
3. ($17$ punktów) $N \le 800$.
4. ($14$ punktów) Istnieje co najwyżej $5$ par $(i, j)$ ($1 \le i \le N, 1 \le j \le N$) spełniających $A_{i, j} \neq$ R.
5. ($16$ punktów) Dla każdego $(i, j)$ ($1 \le i \le N-1, 1 \le j \le N-1$), wśród $A_{i, j}$, $A_{i, j+1}$, $A_{i+1, j}$, $A_{i+1, j+1}$ występują co najmniej $3$ znaki R.
6. ($36$ punktów) Brak dodatkowych ograniczeń.

Wejście

Wejście podawane jest w następującym formacie:

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}

Wyjście

Wypisz w $1$ wierszu maksymalną liczbę kwiatów, jaką może zasadzić dyrektor K.

Przykład 1

Wejście

3
RYR
YBY
BYY

Wyjście

5

Jeśli przyjmiemy $r = 1$ oraz $(x, y) = (2, 2)$, a także wybierzemy niebieski jako $c_0$ i żółty jako $c_1$, możemy zasadzić $5$ kwiatów, jak pokazano na poniższym rysunku. Kolor tła oznacza kolor kwiatu, który można zasadzić w danym sektorze.

Ponieważ nie da się zasadzić $6$ ani więcej kwiatów, wypisujemy $5$.

Ten przykład wejściowy spełnia ograniczenia podzadań $1, 2, 3, 6$.

Przykład 2

Wejście

9
YYRYBBBYR
BYYRRBYBB
RBRRBRBBY
RYRBRYRBR
YYBRYYYRB
RRYBRYRBR
RBYRBRBRB
BRYYRBBBR
RBBBYBRRY

Wyjście

25

Jeśli przyjmiemy $r = 3$ oraz $(x, y) = (5, 6)$, a także wybierzemy żółty jako $c_0$, żółty jako $c_1$, czerwony jako $c_2$ i niebieski jako $c_3$, możemy zasadzić $25$ kwiatów, jak pokazano na poniższym rysunku. Kolor tła oznacza kolor kwiatu, który można zasadzić w danym sektorze.

Ponieważ nie da się zasadzić $26$ ani więcej kwiatów, wypisujemy $25$.

Ten przykład wejściowy spełnia ograniczenia podzadań $2, 3, 6$.

Przykład 3

Wejście

6
RBYRBY
BYRBYR
YRBYRB
RBYRBY
BYRBYR
YRBYRB

Wyjście

1

Ten przykład wejściowy spełnia ograniczenia podzadań $2, 3, 6$.

Przykład 4

Wejście

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

Wyjście

85

Ten przykład wejściowy spełnia ograniczenia podzadań $2, 3, 4, 5, 6$.

Przykład 5

Wejście

10
RRRRRRRRRR
RYRRRRRRRR
RRRRYRRRRR
RBRRRRRRRR
RRRRRRRRYR
RBRRRRRRRR
RRRRBRRRRR
RBRRRRRRRR
RRRRRRRRYR
RRRRRRRRRR

Wyjście

25

Ten przykład wejściowy spełnia ograniczenia podzadań $2, 3, 5, 6$.