โจทย์ปัญหา

สวน 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$ ให้ปลูกดอกไม้สี $c_d$ ลงในแปลง $(x', y')$
   • หาก $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$ คะแนน) มี $(i, j)$ ($1 \le i \le N, 1 \le j \le N$) ที่สอดคล้องกับ $A_{i, j} \neq$ R ไม่เกิน $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}$ จะมี R อยู่อย่างน้อย $3$ ตัว
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$