Есептің шарты

JOI бағы тігінен $N$ жолдан және көлденеңінен $N$ бағаннан тұратын торға бөлінген шаршы пішіндес. Жоғарыдан санағанда $i$-ші жолда ($1 \le i \le N$) және солдан санағанда $j$-ші бағанда ($1 \le j \le N$) орналасқан ұяшық $(i, j)$ телімі деп аталады.

JOI бағының топырағы онша құнарлы болмағандықтан, әр телімге белгілі бір $1$ түсті гүлден ең көп дегенде $1$ тал ғана отырғызуға болады. Нақтырақ айтқанда, $(i, j)$ телімінде $A_{i, j} =$ R болғанда қызыл, $A_{i, j} =$ Y болғанда сары, ал $A_{i, j} =$ B болғанда көк түсті гүлден ең көп дегенде $1$ тал ғана отырғызуға болады.

Осы бақтың басқарушысы K директор аэрофотосуретке түсіргенде бақ әдемі көрінуі үшін гүлдерді келесі тәртіппен отырғызбақшы:

1. Өлшемді білдіретін $r$ бүтін санын таңдау. Бірақ $0 \le r \le (N-1) \div 2$ шарты орындалуы тиіс.
2. Центрді білдіретін $(x, y)$ телімін таңдау. Бірақ $r+1 \le x \le N-r$ және $r+1 \le y \le N-r$ шарттары орындалуы тиіс.
3. $c_0, c_1, c_2, \dots, c_r$ түстерін әрқайсысын қызыл, сары және көк түстердің ішінен таңдап бекіту.
4. Әрбір $(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$ — бүтін сан.

Ішкі есептер

1. ($4$ ұпай) $N = 3$.
2. ($13$ ұпай) $N \le 50$.
3. ($17$ ұпай) $N \le 800$.
4. ($14$ ұпай) $A_{i, j} \neq$ R шартын қанағаттандыратын $(i, j)$ ($1 \le i \le N, 1 \le j \le N$) жұптарының саны $5$-тен аспайды.
5. ($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 бар.
6. ($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}

Шығыс деректер

K директор отырғыза алатын гүлдердің ең көп санын $1$ жолда шығарыңыз.

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$-ішкі есептердің шектеулерін қанағаттандырады.