시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 9 9 8 100.000%

문제

JOI 君は文化祭でのクラスの出し物を宣伝するため,ポスターを作った.そのポスターは N 行 N 列のマス目の形をしており,各マスは赤,緑,青のいずれかの色で塗られている.ポスターの上から i 行目,左から j 列目 (1 ≦ i ≦ N1 ≦ j ≦ N) にあるマスの色は,Si,j= `R' のとき赤色,Si,j= `G' のとき緑色,Si,j= `B' のとき青色である.

しかし,このポスターにクラスのみんなは満足してはくれなかった.話し合いの結果,マス目の形は変えずに色の配置を変えることで,新しいポスターを作ることに決まった.新しいポスターの上から i 行目,左から j 列目 (1 ≦ i ≦ N1 ≦ j ≦ N) にあるマスの色は,Ti,j= `R' のとき赤色,Ti,j= `G' のとき緑色,i,j= `B' のとき青色となるようにする.

JOI 君は今あるポスターに以下のいずれかの作業を繰り返し行うことで,新しいポスターを作ることにした.

  • マスを一つ選び,そのマスの色を好きな色に塗りなおす.
  • ポスター全体を 90° 時計回りに回転させる.このとき,もともと上から i 行目,左から j 列目 (1 ≦ i ≦ N1 ≦ j ≦ N) にあるマスは,上から j 行目,左から N-i+1 列目にあるマスに移動する.
  • ポスター全体を 90° 反時計回りに回転させる.このとき,もともと上から i 行目,左から j 列目 (1 ≦ i ≦ N1 ≦ j ≦ N) にあるマスは,上から N-j+1 行目,左から i 列目にあるマスに移動する.

JOI 君はどの作業をするにも 1 分かかる.JOI 君が作ったポスター,新しく作るポスターの情報が与えられたとき,JOI 君が新しいポスターを作るのに最短で何分かかるかを求めるプログラムを作成せよ.

입력

入力は以下の形式で標準入力から与えられる.

N
S1,1 … S1,N
:
SN,1 … SN,N
T1,1 … T1,N
:
TN,1 … TN,N

출력

新しいポスターを作るのに最短で何分かかるかを 1 行で出力せよ.

제한

  • 1 ≦ N ≦ 500
  • Si,j は `R',`G',`B' のいずれかである.
  • Ti,j は `R',`G',`B' のいずれかである.

예제 입력 1

3
RRR
GGG
BBB
RRR
RRR
RRR

예제 출력 1

6
  • 2 行目と 3 行目にあるマス目をすべて赤色に塗りかえればよい.これには 6 分かかる.

예제 입력 2

3
RRR
GGG
BBB
RGB
RGB
RGB

예제 출력 2

1
  • ポスター全体を 90° 反時計回りに回転させればよい.これには 1 分かかる.

예제 입력 3

6
RRRBBB
RRRBBB
RRRBBB
GGGRRG
GGGRRG
GGGBBR
RRRGGG
RRRGGG
RRRGGG
BBBRRB
BBBRRB
BBBGGR

예제 출력 3

10