ポスター (Poster)

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

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

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

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

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

• \(1 \leqq N \leqq 500\)．
• \(S_{i,j}\) は R，G，B のいずれかである．
• \(T_{i,j}\) は R，G，B のいずれかである．

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

\(N\)
\(S_{1,1} \cdots S_{1,N}\)
\(\vdots\)
\(S_{N,1} \cdots S_{N,N}\)
\(T_{1,1} \cdots T_{1,N}\)
\(\vdots\)
\(T_{N,1} \cdots T_{N,N}\)

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

JOI 2020 · JCIOI · CC BY-SA 4.0