Deskripsi Masalah

Taman JOI berbentuk persegi yang dibagi menjadi petak-petak berukuran $N$ baris secara vertikal dan $N$ kolom secara horizontal. Petak pada baris ke-$i$ dari atas ($1 \le i \le N$) dan kolom ke-$j$ dari kiri ($1 \le j \le N$) disebut bagian $(i, j)$.

Karena Taman JOI tidak diberkahi tanah yang terlalu subur, di setiap bagian hanya dapat ditanam paling banyak $1$ bunga dari $1$ jenis warna tertentu. Secara spesifik, di bagian $(i, j)$, hanya dapat ditanam paling banyak $1$ bunga berwarna merah jika $A_{i, j} =$ R, kuning jika $A_{i, j} =$ Y, dan biru jika $A_{i, j} =$ B.

Di sini, Direktur K, pengelola taman ini, berencana menanam bunga dengan prosedur berikut agar terlihat indah saat diambil foto udara:

1. Menentukan bilangan bulat $r$ yang menyatakan ukuran. Namun, harus memenuhi $0 \le r \le (N-1) \div 2$.
2. Menentukan bagian $(x, y)$ yang menyatakan pusat. Namun, harus memenuhi $r+1 \le x \le N-r$ dan $r+1 \le y \le N-r$.
3. Memilih dan menentukan warna $c_0, c_1, c_2, \dots, c_r$ masing-masing dari merah, kuning, dan biru.
4. Untuk setiap bagian $(x', y')$, tanam bunga sesuai dengan $d = |x'-x| + |y'-y|$ berdasarkan aturan berikut, dengan $|t|$ menyatakan nilai mutlak dari $t$:
   • Jika $d \le r$, tanam bunga berwarna $c_d$ di bagian $(x', y')$.
   • Jika $d > r$, jangan tanam bunga di bagian $(x', y')$.

Diberikan ukuran taman dan informasi warna bunga yang dapat ditanam di setiap bagian, buatlah program untuk mencari jumlah maksimum bunga yang dapat ditanam oleh Direktur K.

Batasan

• $3 \le N \le 3\,500$.
• $A_{i, j}$ adalah salah satu dari R, Y, B ($1 \le i \le N, 1 \le j \le N$).
• $N$ adalah bilangan bulat.

Subsoal

1. ($4$ poin) $N = 3$.
2. ($13$ poin) $N \le 50$.
3. ($17$ poin) $N \le 800$.
4. ($14$ poin) Terdapat paling banyak $5$ pasang $(i, j)$ ($1 \le i \le N, 1 \le j \le N$) yang memenuhi $A_{i, j} \neq$ R.
5. ($16$ poin) Untuk setiap $(i, j)$ ($1 \le i \le N-1, 1 \le j \le N-1$), terdapat setidaknya $3$ buah R di antara $A_{i, j}$, $A_{i, j+1}$, $A_{i+1, j}$, $A_{i+1, j+1}$.
6. ($36$ poin) Tidak ada batasan tambahan.

Masukan

Masukan diberikan dalam format berikut:

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}

Keluaran

Cetak jumlah maksimum bunga yang dapat ditanam oleh Direktur K dalam $1$ baris.

Contoh 1

Masukan

3
RYR
YBY
BYY

Keluaran

5

Jika kita menetapkan $r = 1$, $(x, y) = (2, 2)$, serta memilih biru sebagai $c_0$ dan kuning sebagai $c_1$, kita dapat menanam $5$ bunga seperti pada gambar di bawah ini. Di sini, warna latar belakang menunjukkan warna bunga yang dapat ditanam di setiap bagian.

Karena tidak ada cara untuk menanam $6$ bunga atau lebih, cetak $5$.

Contoh masukan ini memenuhi batasan Subsoal $1, 2, 3, 6$.

Contoh 2

Masukan

9
YYRYBBBYR
BYYRRBYBB
RBRRBRBBY
RYRBRYRBR
YYBRYYYRB
RRYBRYRBR
RBYRBRBRB
BRYYRBBBR
RBBBYBRRY

Keluaran

25

Jika kita menetapkan $r = 3$, $(x, y) = (5, 6)$, serta memilih kuning sebagai $c_0$, kuning sebagai $c_1$, merah sebagai $c_2$, dan biru sebagai $c_3$, kita dapat menanam $25$ bunga seperti pada gambar di bawah ini. Di sini, warna latar belakang menunjukkan warna bunga yang dapat ditanam di setiap bagian.

Karena tidak ada cara untuk menanam $26$ bunga atau lebih, cetak $25$.

Contoh masukan ini memenuhi batasan Subsoal $2, 3, 6$.

Contoh 3

Masukan

6
RBYRBY
BYRBYR
YRBYRB
RBYRBY
BYRBYR
YRBYRB

Keluaran

1

Contoh masukan ini memenuhi batasan Subsoal $2, 3, 6$.

Contoh 4

Masukan

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

Keluaran

85

Contoh masukan ini memenuhi batasan Subsoal $2, 3, 4, 5, 6$.

Contoh 5

Masukan

10
RRRRRRRRRR
RYRRRRRRRR
RRRRYRRRRR
RBRRRRRRRR
RRRRRRRRYR
RBRRRRRRRR
RRRRBRRRRR
RBRRRRRRRR
RRRRRRRRYR
RRRRRRRRRR

Keluaran

25

Contoh masukan ini memenuhi batasan Subsoal $2, 3, 5, 6$.