Aufgabenstellung

Der JOI-Garten hat die Form eines Quadrats, das gitterförmig in vertikal $N$ Zeilen und horizontal $N$ Spalten unterteilt ist. Das Feld in der $i$-ten Zeile von oben ($1 \le i \le N$) und der $j$-ten Spalte von links ($1 \le j \le N$) wird als Parzelle $(i, j)$ bezeichnet.

Da der JOI-Garten keinen besonders guten Boden hat, kann in jeder Parzelle höchstens $1$ Blume von $1$ bestimmten Farbe gepflanzt werden. Konkret kann in Parzelle $(i, j)$ für $A_{i, j} =$ R eine rote, für $A_{i, j} =$ Y eine gelbe und für $A_{i, j} =$ B eine blaue Blume gepflanzt werden, und zwar höchstens $1$ Stück.

Nun möchte Direktor K, der Verwalter dieses Gartens, Blumen nach folgendem Verfahren pflanzen, damit der Garten auf Luftbildern gut aussieht:

1. Lege eine ganze Zahl $r$ fest, die die Größe darstellt. Dabei muss $0 \le r \le (N-1) \div 2$ gelten.
2. Lege eine Parzelle $(x, y)$ fest, die das Zentrum darstellt. Dabei müssen $r+1 \le x \le N-r$ und $r+1 \le y \le N-r$ gelten.
3. Wähle die Farben $c_0, c_1, c_2, \dots, c_r$ jeweils aus Rot, Gelb und Blau aus.
4. Pflanze für jede Parzelle $(x', y')$ in Abhängigkeit von $d = |x'-x| + |y'-y|$ nach folgenden Regeln Blumen, wobei $|t|$ den Absolutbetrag von $t$ bezeichnet:
   • Wenn $d \le r$ gilt, wird in Parzelle $(x', y')$ eine Blume der Farbe $c_d$ gepflanzt.
   • Wenn $d > r$ gilt, wird in Parzelle $(x', y')$ keine Blume gepflanzt.

Schreibe ein Programm, das bei gegebener Größe des Gartens und Informationen über die möglichen Blumenfarben in jeder Parzelle die maximale Anzahl an Blumen bestimmt, die Direktor K pflanzen kann.

Bedingungen

• $3 \le N \le 3\,500$.
• $A_{i, j}$ ist eines der Zeichen R, Y, B ($1 \le i \le N, 1 \le j \le N$).
• $N$ ist eine ganze Zahl.

Teilaufgaben

1. ($4$ Punkte) $N = 3$.
2. ($13$ Punkte) $N \le 50$.
3. ($17$ Punkte) $N \le 800$.
4. ($14$ Punkte) Es gibt höchstens $5$ Paare $(i, j)$ ($1 \le i \le N, 1 \le j \le N$) mit $A_{i, j} \neq$ R.
5. ($16$ Punkte) Für jedes $(i, j)$ ($1 \le i \le N-1, 1 \le j \le N-1$) kommt unter $A_{i, j}$, $A_{i, j+1}$, $A_{i+1, j}$, $A_{i+1, j+1}$ mindestens $3$-mal R vor.
6. ($36$ Punkte) Keine weiteren Einschränkungen.

Eingabe

Die Eingabe erfolgt im folgenden 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}

Ausgabe

Gib die maximale Anzahl an Blumen, die Direktor K pflanzen kann, in $1$ Zeile aus.

Beispiel 1

Eingabe

3
RYR
YBY
BYY

Ausgabe

5

Wenn man $r = 1$ und $(x, y) = (2, 2)$ setzt sowie Blau als $c_0$ und Gelb als $c_1$ wählt, kann man wie in der Abbildung unten $5$ Blumen pflanzen. Dabei gibt die Hintergrundfarbe an, welche Blumenfarbe in der jeweiligen Parzelle gepflanzt werden kann.

Da es keine Möglichkeit gibt, $6$ oder mehr Blumen zu pflanzen, wird $5$ ausgegeben.

Dieses Eingabebeispiel erfüllt die Bedingungen der Teilaufgaben $1, 2, 3, 6$.

Beispiel 2

Eingabe

9
YYRYBBBYR
BYYRRBYBB
RBRRBRBBY
RYRBRYRBR
YYBRYYYRB
RRYBRYRBR
RBYRBRBRB
BRYYRBBBR
RBBBYBRRY

Ausgabe

25

Wenn man $r = 3$ und $(x, y) = (5, 6)$ setzt sowie Gelb als $c_0$, Gelb als $c_1$, Rot als $c_2$ und Blau als $c_3$ wählt, kann man wie in der Abbildung unten $25$ Blumen pflanzen. Dabei gibt die Hintergrundfarbe an, welche Blumenfarbe in der jeweiligen Parzelle gepflanzt werden kann.

Da es keine Möglichkeit gibt, $26$ oder mehr Blumen zu pflanzen, wird $25$ ausgegeben.

Dieses Eingabebeispiel erfüllt die Bedingungen der Teilaufgaben $2, 3, 6$.

Beispiel 3

Eingabe

6
RBYRBY
BYRBYR
YRBYRB
RBYRBY
BYRBYR
YRBYRB

Ausgabe

1

Dieses Eingabebeispiel erfüllt die Bedingungen der Teilaufgaben $2, 3, 6$.

Beispiel 4

Eingabe

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

Ausgabe

85

Dieses Eingabebeispiel erfüllt die Bedingungen der Teilaufgaben $2, 3, 4, 5, 6$.

Beispiel 5

Eingabe

10
RRRRRRRRRR
RYRRRRRRRR
RRRRYRRRRR
RBRRRRRRRR
RRRRRRRRYR
RBRRRRRRRR
RRRRBRRRRR
RBRRRRRRRR
RRRRRRRRYR
RRRRRRRRRR

Ausgabe

25

Dieses Eingabebeispiel erfüllt die Bedingungen der Teilaufgaben $2, 3, 5, 6$.