Tehtävänanto

JOI-puutarha on neliön muotoinen alue, joka on jaettu ruudukoksi, jossa on pystysuunnassa $N$ riviä ja vaakasuunnassa $N$ saraketta. Ylhäältä lukien $i$-nnen rivin ($1 \le i \le N$) ja vasemmalta lukien $j$-nnen sarakkeen ($1 \le j \le N$) ruutua kutsutaan lohkoksi $(i, j)$.

Koska JOI-puutarhan maaperä ei ole kovin ravinteikas, kuhunkin lohkoon voidaan istuttaa enintään $1$ kukka $1$ tiettyä väriä. Tarkemmin sanoen lohkoon $(i, j)$ voidaan istuttaa enintään $1$ punainen kukka, kun $A_{i, j} =$ R, keltainen kukka, kun $A_{i, j} =$ Y, ja sininen kukka, kun $A_{i, j} =$ B.

Puutarhaa hoitava johtaja K aikoo istuttaa kukat seuraavalla menettelyllä, jotta puutarha näyttäisi hyvältä ilmakuvassa:

1. Päätä kokoa kuvaava kokonaisluku $r$. Tässä on pädettävä $0 \le r \le (N-1) \div 2$.
2. Päätä keskipistettä kuvaava lohko $(x, y)$. Tässä on pädettävä $r+1 \le x \le N-r$ ja $r+1 \le y \le N-r$.
3. Valitse ja päätä värit $c_0, c_1, c_2, \dots, c_r$, kukin punaisesta, keltaisesta ja sinisestä.
4. Istuta kuhunkin lohkoon $(x', y')$ kukka etäisyyden $d = |x'-x| + |y'-y|$ perusteella seuraavien sääntöjen mukaisesti, missä $|t|$ tarkoittaa luvun $t$ itseisarvoa:
   • Jos $d \le r$, lohkoon $(x', y')$ istutetaan värin $c_d$ kukka.
   • Jos $d > r$, lohkoon $(x', y')$ ei istuteta kukkaa.

Kun annetaan puutarhan koko sekä tiedot kuhunkin lohkoon istutettavissa olevien kukkien väreistä, kirjoita ohjelma, joka etsii suurimman mahdollisen kukkien määrän, jonka johtaja K voi istuttaa.

Rajoitukset

• $3 \le N \le 3\,500$.
• $A_{i, j}$ on jokin merkeistä R, Y, B ($1 \le i \le N, 1 \le j \le N$).
• $N$ on kokonaisluku.

Osatehtävät

1. ($4$ pistettä) $N = 3$.
2. ($13$ pistettä) $N \le 50$.
3. ($17$ pistettä) $N \le 800$.
4. ($14$ pistettä) On korkeintaan $5$ sellaista paria $(i, j)$ ($1 \le i \le N, 1 \le j \le N$), joilla $A_{i, j} \neq$ R.
5. ($16$ pistettä) Mille tahansa $(i, j)$ ($1 \le i \le N-1, 1 \le j \le N-1$) merkkien $A_{i, j}$, $A_{i, j+1}$, $A_{i+1, j}$, $A_{i+1, j+1}$ joukossa on vähintään $3$ merkkiä R.
6. ($36$ pistettä) Ei lisärajoituksia.

Syöte

Syöte annetaan seuraavassa muodossa:

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}

Tuloste

Tulosta $1$ riville suurin mahdollinen kukkien määrä, jonka johtaja K voi istuttaa.

Esimerkki 1

Syöte

3
RYR
YBY
BYY

Tuloste

5

Jos asetetaan $r = 1$ ja $(x, y) = (2, 2)$ sekä valitaan sininen väriksi $c_0$ ja keltainen väriksi $c_1$, voidaan istuttaa $5$ kukkaa alla olevan kuvan mukaisesti. Tässä taustaväri osoittaa, minkä värisen kukan kuhunkin lohkoon voi istuttaa.

Koska ei ole mitään tapaa istuttaa $6$ tai useampaa kukkaa, tulostetaan $5$.

Tämä syöteesimerkki täyttää osatehtävien $1, 2, 3, 6$ rajoitukset.

Esimerkki 2

Syöte

9
YYRYBBBYR
BYYRRBYBB
RBRRBRBBY
RYRBRYRBR
YYBRYYYRB
RRYBRYRBR
RBYRBRBRB
BRYYRBBBR
RBBBYBRRY

Tuloste

25

Jos asetetaan $r = 3$ ja $(x, y) = (5, 6)$ sekä valitaan keltainen väriksi $c_0$, keltainen väriksi $c_1$, punainen väriksi $c_2$ ja sininen väriksi $c_3$, voidaan istuttaa $25$ kukkaa alla olevan kuvan mukaisesti. Tässä taustaväri osoittaa, minkä värisen kukan kuhunkin lohkoon voi istuttaa.

Koska ei ole mitään tapaa istuttaa $26$ tai useampaa kukkaa, tulostetaan $25$.

Tämä syöteesimerkki täyttää osatehtävien $2, 3, 6$ rajoitukset.

Esimerkki 3

Syöte

6
RBYRBY
BYRBYR
YRBYRB
RBYRBY
BYRBYR
YRBYRB

Tuloste

1

Tämä syöteesimerkki täyttää osatehtävien $2, 3, 6$ rajoitukset.

Esimerkki 4

Syöte

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

Tuloste

85

Tämä syöteesimerkki täyttää osatehtävien $2, 3, 4, 5, 6$ rajoitukset.

Esimerkki 5

Syöte

10
RRRRRRRRRR
RYRRRRRRRR
RRRRYRRRRR
RBRRRRRRRR
RRRRRRRRYR
RBRRRRRRRR
RRRRBRRRRR
RBRRRRRRRR
RRRRRRRRYR
RRRRRRRRRR

Tuloste

25

Tämä syöteesimerkki täyttää osatehtävien $2, 3, 5, 6$ rajoitukset.